Гипотеза Хивуда - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:40:48Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:38, 1 сентября 2022

2022-09-01T03:38:40Z

188.17.80.207: /* Теорема о нижней границе хроматического числа поверхности */

2019-12-31T17:40:55Z

‎Теорема о нижней границе хроматического числа поверхности

Gaporf: /* Теорема о нижней границе хроматического числа поверхности */

2019-12-25T21:15:40Z

‎Теорема о нижней границе хроматического числа поверхности

Gaporf: /* Теорема о нижней границе хроматического числа поверхности */ доказал беспруфный факт

2019-12-24T11:14:17Z

‎Теорема о нижней границе хроматического числа поверхности: доказал беспруфный факт

Gaporf в 19:20, 3 декабря 2019

2019-12-03T19:20:02Z

Gaporf в 20:24, 2 декабря 2019

2019-12-02T20:24:10Z

Gaporf: Первая версия

2019-12-01T14:32:21Z

Первая версия

Новая страница

{{Определение
|id = Heawood number
|definition =
'''Хроматическим числом поверхности поверхности <tex>S_n</tex>''' или '''<tex>n</tex>-ым числом Хивуда''' называется число <tex>\chi \left( S_n \right)</tex>, равное максимальному хроматическому числу графа, который можно уложить на поверхность <tex>n</tex>-ого рода.
}}

{{Теорема
|about=
Теорема Хивуда о раскраске карт
|statement=
Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода определяется формулой <tex>\chi \left( S_n \right) = \left[ \dfrac{ 7 + \sqrt{1 + 48n} }{ 2 } \right]</tex>
|proof=

Для начала докажем <tex>\chi \left(S_n\right) \leqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>

Пусть задан граф <tex>G</tex> с <tex>V</tex> вершина, <tex>E</tex> рёбрами и <tex>F</tex> гранями, также будем считать, что <tex>G</tex> <tex>-</tex> триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности <tex>n</tex>-ого рода). Обозначим за <tex>d</tex> <tex>-</tex> среднюю степень вершины графа <tex>G</tex>, тогда должно быть справедливым следующее равенство:

<tex>dV = 2E = 3F</tex>.

Воспользуемся следующей формулой Эйлера

<tex>V - E + F = 2 - 2 n</tex>

Откуда <tex>E = V + F + 2 (n - 1)</tex> и <tex>F = 2 V + 4 (n - 1)</tex> и подставляя в первое равенство получаем

<tex>dV = 6V + 12(n - 1)</tex>

<tex>d = 6 + \dfrac{12(n - 1)}{V}</tex>

Поскольку <tex>d \leqslant V - 1</tex>, то получаем, что

<tex>V - 1\geqslant 6 + \dfrac{12(n - 1)}{V}</tex>.

Найдя единственный положительный корень неравенства получаем

<tex>V \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>

Обозначим за <tex>H(n) = \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Если <tex> V \leqslant H(n)</tex>, то тогда граф <tex>G</tex> очевидно можно раскрасить в <tex>H(n)</tex> цветов и неравенство верное. Допустим, что <tex>V > H(n)</tex>, тогда

<tex> d < 6 + \dfrac{12(n - 1)}{H(n)} = H(n) - 1</tex>

Значит в такое графе существует хотя бы одна вершина степени не больше <tex>H(n) - 2</tex>, стянем её с любой соседней и получим новый граф <tex>G'</tex> с <tex>V - 1</tex> вершинами. Если <tex>V - 1 = H(n)</tex>, то граф <tex>G'</tex> можно раскрасить в <tex>H(n)</tex> цветов, значит и сам граф <tex>G</tex> можно также раскрасить в <tex>H(n)</tex> цветов, иначе снова повторим наш алгоритм.

Осталось доказать нижнюю границу для <tex>\chi \left(S_n\right)</tex>, для этого воспользуемся неравенством

<tex>n \geqslant \gamma\left(K_p\right) = \left\{\frac{(p - 3)(p - 4)}{12}\right\}</tex>, функция монотонно возрастает при <tex>p \geqslant 4</tex>, и для любого <tex>n</tex> наибольшее значение функция <tex>\left\{\frac{(p - 3)(p - 4)}{12}\right\}</tex> достигается при <tex>p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Поскольку <tex>\chi\left(K_p\right) = p</tex>, откуда получаем, что <tex>H(n)</tex> неулучшаемая нижняя граница для числа <tex>\chi\left(S_n\right)</tex>.

}}

==См. также==
* [[Хроматическое число планарного графа]]
* [[Проблема четырёх красок]]
* [[Формула Эйлера]]

==Источники информации==
* [https://en.wikipedia.org/wiki/Heawood_conjecture Wikipedia {{---}} Heawood conjecture]
* [https://oeis.org/A000934 Последовательность чисел Хивуда]
* Харари - Теория графов (стр. 162 - 164)

← Предыдущая		Версия 16:40, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|id = Heawood number		\|id = Heawood number

← Предыдущая		Версия 03:38, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|id = Heawood number		\|id = Heawood number

@@ Строка 14: / Строка 14: @@
 |proof=
-Воспользуемся формулой Эйлера <tex>V + F - E = 2 - 2n</tex>, тогда давайте докажем нижнюю границу на <tex>E</tex>, поскольку каждая грань может быть треугольником, то для <tex>E</tex> будет неулучшаемая нижняя граница:
+Воспользуемся формулой Эйлера <tex>V + F - E = 2 - 2n</tex>. Давайте докажем нижнюю границу на <tex>E</tex>. Максимизируем число граней: каждая из них может быть треугольником. Тогда для <tex>E</tex> существует неулучшаемая нижняя граница:
 <tex>E \geqslant 3 \left( V - 2 + 2n \right)</tex>

@@ Строка 14: / Строка 14: @@
 |proof=
-Воспользуемся формулой Эйлера <tex>V + F - E = 2 - 2n</tex>, тогда если представить самый худший случай, что каждая грань {{---}} треугольник, то отсюда получаем следующее неравенство:
+Воспользуемся формулой Эйлера <tex>V + F - E = 2 - 2n</tex>, тогда давайте докажем нижнюю границу на <tex>E</tex>, поскольку каждая грань может быть треугольником, то для <tex>E</tex> будет неулучшаемая нижняя граница:
 <tex>E \geqslant 3 \left( V - 2 + 2n \right)</tex>

@@ Строка 14: / Строка 14: @@
 |proof=
-В качестве доказательства воспользуемся теоремой Рингеля и Янгса о минимальном роде поверхности, на которую можно уложить граф <tex>K_p</tex>, а именно <tex>n = \gamma \left( K_p \right) \geqslant \left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex>, функция монотонно возрастает при <tex>p \geqslant 4</tex>, и для любого <tex>n</tex> наибольшее значение функция <tex>\left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex> достигается при <tex>p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Поскольку <tex>\chi\left(K_p\right) = p</tex>, откуда получаем, что <tex>\chi \left( S_n \right) \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>.
+Воспользуемся формулой Эйлера <tex>V + F - E = 2 - 2n</tex>, тогда если представить самый худший случай, что каждая грань {{---}} треугольник, то отсюда получаем следующее неравенство:
 }}

@@ Строка 4: / Строка 4: @@
 '''Хроматическим числом поверхности поверхности <tex>S_n</tex>''' или '''<tex>n</tex>-ым числом Хивуда''' называется число <tex>\chi \left( S_n \right)</tex>, равное максимальному хроматическому числу графа, который можно уложить на поверхность <tex>n</tex>-ого рода.
 }}
 {{Теорема
@@ Строка 9: / Строка 11: @@
 Теорема Рингеля и Янгса
 |statement=
-Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода <tex>\chi \left( S_n \right) \geqslant \left\{ \dfrac{7 + \sqrt{1 + 48n}}{2} \right\}</tex>.
+Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода <tex>\chi \left( S_n \right) \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>.
 |proof=
-В качестве доказательства воспользуемся теоремой Рингеля и Янгса о минимальном роде поверхности, на которую можно уложить граф <tex>K_p</tex>, а именно <tex>n \left( K_p \right) \geqslant \left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex>, функция монотонно возрастает при <tex>p \geqslant 4</tex>, и для любого <tex>n</tex> наибольшее значение функция <tex>\left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex> достигается при <tex>p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Поскольку <tex>\chi\left(K_p\right) = p</tex>, откуда получаем, что <tex>\chi \left( S_n \right) \geqslant \left\{ \dfrac{7 + \sqrt{1 + 48n}}{2} \right\}</tex>.
+В качестве доказательства воспользуемся теоремой Рингеля и Янгса о минимальном роде поверхности, на которую можно уложить граф <tex>K_p</tex>, а именно <tex>n = \gamma \left( K_p \right) \geqslant \left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex>, функция монотонно возрастает при <tex>p \geqslant 4</tex>, и для любого <tex>n</tex> наибольшее значение функция <tex>\left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex> достигается при <tex>p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Поскольку <tex>\chi\left(K_p\right) = p</tex>, откуда получаем, что <tex>\chi \left( S_n \right) \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>.
 }}
 {{Теорема
@@ Строка 22: / Строка 26: @@
 |proof=
-Пусть задан граф <tex>G</tex> с <tex>V</tex> вершина, <tex>E</tex> рёбрами и <tex>F</tex> гранями, также будем считать, что <tex>G</tex> <tex>-</tex> триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности <tex>n</tex>-ого рода). Обозначим за <tex>d</tex> <tex>-</tex> среднюю степень вершины графа <tex>G</tex>, тогда должно быть справедливым следующее равенство:
+Пусть задан граф <tex>G</tex> с <tex>V</tex> вершина, <tex>E</tex> рёбрами и <tex>F</tex> гранями, также будем считать, что <tex>G</tex> {{---}} триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности <tex>n</tex>-ого рода). Обозначим за <tex>d</tex> {{---}} среднюю степень вершины графа <tex>G</tex>, тогда должно быть справедливым следующее равенство:
-<tex>dV = 2E = 3F</tex>.
+<tex>dV = 2E = 3F</tex>
-Воспользуемся следующей формулой Эйлера
+Воспользуемся [[формула Эйлера | формулой Эйлера]] <tex>V - E + F = 2 - 2 n</tex>, откуда
-<tex>V - E + F = 2 - 2 n</tex>
+<tex>E = V + F + 2 (n - 1)</tex> и <tex>F = 2 V + 4 (n - 1)</tex>
-Откуда <tex>E = V + F + 2 (n - 1)</tex> и <tex>F = 2 V + 4 (n - 1)</tex> и подставляя в первое равенство получаем
+и подставляя в первое равенство получаем
 <tex>dV = 6V + 12(n - 1)</tex>
@@ Строка 36: / Строка 40: @@
 <tex>d = 6 + \dfrac{12(n - 1)}{V}</tex>
-Поскольку <tex>d \leqslant V - 1</tex>, то получаем, что
+Поскольку <tex>d \leqslant V - 1</tex>, то
-<tex>V - 1\geqslant 6 + \dfrac{12(n - 1)}{V}</tex>.
+<tex>V - 1\geqslant 6 + \dfrac{12(n - 1)}{V}</tex>
-Найдя единственный положительный корень неравенства получаем
+Найдём единственный положительный корень неравенства
 <tex>V \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>
 Обозначим за <tex>H(n) = \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Если <tex> V \leqslant H(n)</tex>, то тогда граф <tex>G</tex> очевидно можно раскрасить в <tex>H(n)</tex> цветов и неравенство верное. Допустим, что <tex>V > H(n)</tex>, тогда
 <tex> d < 6 + \dfrac{12(n - 1)}{H(n)} = H(n) - 1</tex>
-Значит в такое графе существует хотя бы одна вершина степени не больше <tex>H(n) - 2</tex>, стянем её с любой соседней и получим новый граф <tex>G'</tex> с <tex>V - 1</tex> вершинами. Если <tex>V - 1 = H(n)</tex>, то граф <tex>G'</tex> можно раскрасить в <tex>H(n)</tex> цветов, значит и сам граф <tex>G</tex> можно также раскрасить в <tex>H(n)</tex> цветов, иначе снова повторим наш алгоритм.
+Значит в такое графе существует хотя бы одна вершина степени не больше <tex>H(n) - 2</tex>, стянем её с любой соседней и получим новый граф <tex>G'</tex> с <tex>V - 1</tex> вершинами. Если <tex>V - 1 = H(n)</tex>, то граф <tex>G'</tex> можно раскрасить в <tex>H(n)</tex> цветов, значит и сам граф <tex>G</tex> можно также раскрасить в <tex>H(n)</tex> цветов, если <tex>V - 1 > H(n)</tex>, то опять найдём вершину степени <tex>H(n) - 2</tex> и снова стянем её и будем продолжать так до тех пор, пока не получим желаемый граф.
 }}
 ==Проблема четырёх красок==
-Заметим, что теорема Хивуда не работает при <tex>n = 0</tex>, поэтому [[проблема четырёх красок]] не может быть доказана с помощью этой теоремы, однако при подстановке <tex>n = 0</tex> получаем, что <tex>\chi \left( S_0 \right) = 4</tex>.
+Заметим, что теорема Хивуда не работает при <tex>n = 0</tex>, поэтому [[проблема четырёх красок]] не может быть доказана с помощью этой теоремы, однако при подстановке <tex>n = 0</tex> получаем <tex>\chi \left( S_0 \right) = 4</tex>.
 ==См. также==
@@ Строка 62: / Строка 68: @@
 * [https://en.wikipedia.org/wiki/Heawood_conjecture Wikipedia {{---}} Heawood conjecture]
 * [https://oeis.org/A000934 Последовательность чисел Хивуда]
-* Харари - Теория графов (стр. 162 - 164)
+* Ф.Харари «Теория графов» {{---}} М.: Мир, 1973 г. {{---}} стр. 162 - 164