В теории графов , в работе Хивуда гипотезы или Рингель-Youngs теорема дает нижнюю границу для количества цветов, которые необходимы для раскраски графа на поверхности данного рода . Для поверхностей рода 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 году предположил, что для данного рода g > 0 минимальное количество цветов, необходимое для окраски всех графов, нарисованных на ориентируемой поверхности этого рода (или, что эквивалентно, для окраски областей любого разбиения поверхности на односвязные области). ) дан кем-то
где - функция пола .
Заменяя род на эйлерову характеристику , мы получаем формулу, которая охватывает как ориентируемый, так и неориентируемый случаи:
Это соотношение выполняется, как показали Рингель и Янгс, для всех поверхностей, кроме бутылки Клейна . Филип Франклин (1930) доказал, что для бутылки Кляйна требуется не более 6 цветов, а не 7, как предсказывает формула. Граф Франклина можно нарисовать на бутылке Клейна таким образом, чтобы сформировать шесть взаимно смежных областей, показывая, что эта граница жесткая.
Верхняя оценка, доказанная в оригинальной короткой статье Хивуда, основана на жадном алгоритме раскраски . Манипулируя эйлеровой характеристикой, можно показать, что каждый граф, вложенный в данную поверхность, должен иметь хотя бы одну вершину степени меньше заданной границы. Если удалить эту вершину и раскрасить остальную часть графа, небольшое количество ребер, инцидентных удаленной вершине, гарантирует, что ее можно будет добавить обратно в граф и раскрасить, не увеличивая необходимое количество цветов за пределами границы. С другой стороны, доказательство более трудное и включает в себя демонстрацию того, что в каждом случае (кроме бутылки Клейна) полный граф с числом вершин, равным заданному количеству цветов, может быть вложен в поверхность.
Пример [ править ]
Тор имеет г = 1, так что χ = 0. Таким образом, как формула состояния, любое разбиение тора на область может быть окрашено , используя в большинстве семи цветов. На рисунке показано подразделение тора, в котором каждая из семи областей примыкает друг к другу; это подразделение показывает, что в данном случае ограничение количества цветов до семи является жестким. Граница этого подразделения образует вложение графа Хивуда на тор.
Ссылки [ править ]
- Франклин, П. (1934). «Шестицветная проблема». Журнал математики и физики Массачусетского технологического института . 13 : 363–379. HDL : 2027 / mdp.39015019892200 . CS1 maint: обескураженный параметр ( ссылка )
- Хивуд, П. Дж. (1890). «Теорема о цвете карты». Ежеквартальный математический журнал . 24 : 332–338. CS1 maint: обескураженный параметр ( ссылка )
- Рингель, Г .; Янгс, JWT (1968). «Решение проблемы раскраски карты Хивуда» . Труды Национальной академии наук Соединенных Штатов Америки . 60 (2): 438–445. DOI : 10.1073 / pnas.60.2.438 . Руководство по ремонту 0228378 . PMC 225066 . PMID 16591648 .
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. «Гипотеза Хивуда» . MathWorld .
