Гипотеза Хивуда

Радиально симметричный семицветный тор - области одного цвета оборачиваются по пунктирным линиям.

8-цветный двойной тор (поверхность второго рода) - пузыри обозначают уникальные комбинации двух областей.

Шестицветная бутылка Клейна, единственное исключение из гипотезы Хивуда.

В теории графов гипотеза Хивуда или теорема Рингеля–Янгса дает нижнюю оценку числа цветов, необходимых для раскраски графа на поверхности данного рода . Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7,... необходимое количество цветов - 4, 7, 8, 9, 10, 11, 12, 12,.... OEIS : A000934 , хроматическое число или число Хивуда .

Гипотеза была сформулирована в 1890 году П. Дж. Хивудом и доказана в 1968 году Герхардом Рингелем и Дж. У. Т. Янгсом . Один случай — неориентируемая бутылка Клейна — оказался исключением из общей формулы. Совершенно другой подход был необходим для гораздо более старой проблемы нахождения количества цветов, необходимых для плоскости или , решенной в 1976 году как теорема о четырех цветах Хакеном сферы и Аппелем . На сфере нижняя оценка проста, тогда как для высших родов простая верхняя оценка была доказана в оригинальной короткой статье Хивуда, содержащей гипотезу. Другими словами, Рингелю, Янгсу и другим пришлось построить крайние примеры для каждого рода g = 1, 2, 3,…. Если g = 12 s + k , то роды распадаются на 12 случаев при k = 0, 1, 2, 3, …., 11. Для упрощения предположим, что случай k установлен, если только конечное число g s вида 12 s + k вызывают сомнения. Тогда года, в которых были урегулированы двенадцать дел, и кем являются следующими:

• 1954, Рингель: дело 5
• 1961, Рингель: дела 3, 7, 10
• 1963, Терри, Уэлч, Янгс: случаи 0, 4
• 1964, Гастин, Янгс: случай 1
• 1965, Гастин: дело 9
• 1966, Янгс: дело 6
• 1967, Рингель, Янгс: случаи 2, 8, 11

Последние семь спорадических исключений были урегулированы следующим образом:

• 1967, Майер: дела 18, 20, 23
• 1968, Рингель, Янгс: случаи 30, 35, 47, 59, и гипотеза доказана.

Официальное заявление

График Франклина .

Перси Джон Хивуд в 1890 году предположил , что для данного рода g > 0 минимальное количество цветов, необходимое для раскраски всех графов, нарисованных на ориентируемой поверхности этого рода (или, что то же самое, для раскрашивания областей любого разбиения поверхности на односвязные регионах) определяется выражением

$\gamma (g)=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor ,$

где $\left\lfloor x\right\rfloor$ это функция пола .

Заменив род на эйлерову характеристику , получим формулу, охватывающую как ориентируемый, так и неориентируемый случаи:

$\gamma (\chi )=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor .$

Это соотношение, как показали Рингель и Янгс, справедливо для всех поверхностей, кроме бутылки Клейна . Филип Франклин (1930) доказал, что для бутылки Клейна требуется не более 6 цветов, а не 7, как предсказывает формула. График Франклина можно нарисовать на бутылке Клейна таким образом, чтобы образовались шесть взаимно смежных областей, показывая, что эта граница точна.

Верхняя оценка, доказанная в оригинальной короткой статье Хивуда, основана на жадном алгоритме раскраски . Манипулируя эйлеровой характеристикой, можно показать, что каждый граф, вложенный в данную поверхность, должен иметь хотя бы одну вершину степени меньше заданной границы. Если удалить эту вершину и раскрасить остальную часть графа, небольшое количество ребер, инцидентных удаленной вершине, гарантирует, что ее можно будет добавить обратно в граф и раскрасить, не увеличивая необходимое количество цветов за пределами границы. В обратном направлении доказательство сложнее и включает в себя показ того, что в каждом случае (кроме бутылки Клейна) на поверхность можно вложить полный граф с числом вершин, равным заданному количеству цветов.

Пример

Разделение тора на семь взаимно смежных областей, требующее семь цветов.

Тор . имеет g = 1, поэтому χ = 0. Следовательно, как утверждает формула, любое подразделение тора на области можно раскрасить не более чем семью цветами На иллюстрации показано подразделение тора, в котором каждая из семи областей примыкает друг к другу; это подразделение показывает, что ограничение количества цветов в семь для этого случая является жестким. Граница этого подразделения образует вложение графа Хивуда в тор.

Интерактивная модель многогранника Силасси , каждая из 7 граней которого примыкает друг к другу. На изображении SVG переместите мышь, чтобы повернуть его.

Ссылки

• Франклин, П. (1934). «Задача шести цветов». Журнал математики и физики Массачусетского технологического института . 13 (1–4): 363–379. дои : 10.1002/sapm1934131363 . hdl : 2027/mdp.39015019892200 .
• Хивуд, П.Дж. (1890). «Теорема о цвете карты». Ежеквартальный математический журнал . 24 : 332–338.
• Рингель, Г .; Янгс, JWT (1968). «Решение задачи раскраски карт Хивуда» . Труды Национальной академии наук Соединенных Штатов Америки . 60 (2): 438–445. Бибкод : 1968PNAS...60..438R . дои : 10.1073/pnas.60.2.438 . МР   0228378 . ПМК   225066 . ПМИД   16591648 .

Внешние ссылки

• Вайсштейн, Эрик В. «Гипотеза Хивуда» . Математический мир .