Гипотеза Хивуда - Heawood conjecture
В теория графов, то Гипотеза Хивуда или Теорема Рингеля – Юнга. дает нижняя граница для количества цветов, которые нужно для раскраска графика на поверхность данного род. Для поверхностей рода 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 = 12s + k, роды распадаются на 12 случаев согласно k = 0,1, 2,3,4,5,6,7,8,9,10,11. Для упрощения предположим, что случай k был установлен, если только конечное число g вида 12s + 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 г., что для данного рода г > 0, минимальное количество цветов, необходимое для окраски всех графов, нарисованных на ориентируемой поверхности этого рода (или, что то же самое, для окраски областей любого разбиения поверхности на односвязные области), определяется выражением
где это функция пола.
Замена рода на Эйлерова характеристика, получаем формулу, охватывающую как ориентируемый, так и неориентируемый случаи:
Это соотношение выполняется, как показали Рингель и Янгс, для всех поверхностей, кроме Бутылка Клейна. Филип Франклин (1930) доказали, что для бутылки Кляйна требуется не более 6 цветов, а не 7, как предсказывает формула. В Граф Франклина может быть нарисован на бутылке Клейна таким образом, чтобы образовать шесть взаимно смежных областей, показывая, что эта граница жесткая.
Верхняя оценка, доказанная в оригинальной короткой статье Хивуда, основана на жадная окраска алгоритм. Манипулируя эйлеровой характеристикой, можно показать, что каждый граф, вложенный в данную поверхность, должен иметь хотя бы одну вершину степени меньше заданной границы. Если удалить эту вершину и раскрасить остальную часть графа, небольшое количество ребер, инцидентных удаленной вершине, гарантирует, что ее можно будет добавить обратно в граф и раскрасить, не увеличивая необходимое количество цветов за пределами границы. С другой стороны, доказательство сложнее и включает в себя демонстрацию того, что в каждом случае (кроме бутылки Клейна) полный график с числом вершин, равным заданному количеству цветов, могут быть вложены на поверхность.
пример
В тор имеет г = 1, поэтому χ = 0. Следовательно, согласно формуле, любое разбиение тора на области можно раскрасить, используя не более семи цветов. На иллюстрации показано подразделение тора, в котором каждая из семи областей примыкает друг к другу; это подразделение показывает, что в данном случае граница семи на количество цветов жесткая. Граница этого подразделения образует вложение График Хивуда на тор.
использованная литература
- Франклин, П. (1934). «Шестицветная проблема». Журнал математики и физики Массачусетского технологического института. 13: 363–379. HDL:2027 / mdp.39015019892200.
- Хивуд, П. Дж. (1890). «Теорема о цвете карты». Ежеквартальный журнал математики. 24: 332–338.
- Рингель, Г.; Янгс, Дж. У. Т. (1968). «Решение проблемы раскраски карты Хивуда». Труды Национальной академии наук Соединенных Штатов Америки. 60 (2): 438–445. Дои:10.1073 / pnas.60.2.438. Г-Н 0228378. ЧВК 225066. PMID 16591648.