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

редактировать

В теории графов используется гипотеза Хивуда или теорема Рингеля – Янгса дает нижнюю границу для количества цветов, которые необходимы для раскраски графа на поверхности заданного род. Для поверхностей рода 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, и гипотеза была доказана.
Содержание
  • 1 Формальное утверждение
  • 2 Пример
  • 3 Ссылки
  • 4 Внешние ссылки
Формальное утверждение
Граф Франклина.

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

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

где ⌊ x ⌋ {\ displaystyle \ left \ lfloor x \ right \ rfloor}\ left \ lfloor x \ right \ rfloor - это функция пола.

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

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

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

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

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

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

Ссылки
Внешние ссылки
Последняя правка сделана 2021-05-23 04:49:42
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте