390
правок
Изменения
Первая версия
{{Определение
|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)
|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)
