Гипотеза Хивуда — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Первая версия)
 
Строка 7: Строка 7:
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
Теорема Хивуда о раскраске карт
+
Теорема Рингеля и Янгса
 
|statement=
 
|statement=
Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода определяется формулой <tex>\chi \left( S_n \right) = \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=
 
|proof=
  
Для начала докажем <tex>\chi \left(S_n\right) \leqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>
+
В качестве доказательства воспользуемся теоремой Рингеля и Янгса о минимальном роде поверхности, на которую можно уложить граф <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>.
 +
}}
 +
 
 +
{{Теорема
 +
|about=
 +
Гипотеза Хивуда
 +
|statement=
 +
Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода <tex>\chi \left( S_n \right) \leqslant \left[ \dfrac{ 7 + \sqrt{1 + 48n} }{ 2 } \right]</tex>.
 +
|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>-</tex> триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности <tex>n</tex>-ого рода). Обозначим за <tex>d</tex> <tex>-</tex> среднюю степень вершины графа <tex>G</tex>, тогда должно быть справедливым следующее равенство:
Строка 41: Строка 49:
  
 
Значит в такое графе существует хотя бы одна вершина степени не больше <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>\chi \left(S_n\right)</tex>, для этого воспользуемся неравенством
+
==Проблема четырёх красок==
 
+
Заметим, что теорема Хивуда не работает при <tex>n = 0</tex>, поэтому [[проблема четырёх красок]] не может быть доказана с помощью этой теоремы, однако при подстановке <tex>n = 0</tex> получаем, что <tex>\chi \left( S_0 \right) = 4</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>.
 
 
 
}}
 
  
 
==См. также==
 
==См. также==

Версия 23:24, 2 декабря 2019

Определение:
Хроматическим числом поверхности поверхности [math]S_n[/math] или [math]n[/math]-ым числом Хивуда называется число [math]\chi \left( S_n \right)[/math], равное максимальному хроматическому числу графа, который можно уложить на поверхность [math]n[/math]-ого рода.


Теорема (Теорема Рингеля и Янгса):
Для любого положительного целого числа [math]n[/math] хроматическое число поверхности [math]n[/math]-ого рода [math]\chi \left( S_n \right) \geqslant \left\{ \dfrac{7 + \sqrt{1 + 48n}}{2} \right\}[/math].
Доказательство:
[math]\triangleright[/math]
В качестве доказательства воспользуемся теоремой Рингеля и Янгса о минимальном роде поверхности, на которую можно уложить граф [math]K_p[/math], а именно [math]n \left( K_p \right) \geqslant \left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}[/math], функция монотонно возрастает при [math]p \geqslant 4[/math], и для любого [math]n[/math] наибольшее значение функция [math]\left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}[/math] достигается при [math]p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right][/math]. Поскольку [math]\chi\left(K_p\right) = p[/math], откуда получаем, что [math]\chi \left( S_n \right) \geqslant \left\{ \dfrac{7 + \sqrt{1 + 48n}}{2} \right\}[/math].
[math]\triangleleft[/math]
Теорема (Гипотеза Хивуда):
Для любого положительного целого числа [math]n[/math] хроматическое число поверхности [math]n[/math]-ого рода [math]\chi \left( S_n \right) \leqslant \left[ \dfrac{ 7 + \sqrt{1 + 48n} }{ 2 } \right][/math].
Доказательство:
[math]\triangleright[/math]

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

[math]dV = 2E = 3F[/math].

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

[math]V - E + F = 2 - 2 n[/math]

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

[math]dV = 6V + 12(n - 1)[/math]

[math]d = 6 + \dfrac{12(n - 1)}{V}[/math]

Поскольку [math]d \leqslant V - 1[/math], то получаем, что

[math]V - 1\geqslant 6 + \dfrac{12(n - 1)}{V}[/math].

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

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

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

[math] d \lt 6 + \dfrac{12(n - 1)}{H(n)} = H(n) - 1[/math]

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

Проблема четырёх красок

Заметим, что теорема Хивуда не работает при [math]n = 0[/math], поэтому проблема четырёх красок не может быть доказана с помощью этой теоремы, однако при подстановке [math]n = 0[/math] получаем, что [math]\chi \left( S_0 \right) = 4[/math].

См. также

Источники информации