390
правок
Изменения
Нет описания правки
{{Теорема
|about=
Теорема Хивуда о раскраске картРингеля и Янгса
|statement=
Для любого положительного целого числа <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>.}} {{Теорема|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>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> цветов, иначе снова повторим наш алгоритм.
}}
==См. также==
