Page 76 - 4496

Можна довести, що хроматичне число планарних графів
менше або дорівнює 5. Однак Августом де Морганом (1850)
була висунута гіпотеза про те, що хроматичне число
планарних графів менше або дорівнює 4. Цій проблемі було
присвячено величезне число математичних робіт. Зрештою,
удалося звести цю проблему до дослідження вірності цієї
гіпотези для досить великої кількості типів графів ( 30 тис.),
що й було зроблено за допомогою комп'ютерів (1976).
Гіпотеза про чотири фарби виявилася справедливою, а сама
проблема перейшла в задачу про спрощення доказу гіпотези
про чотири фарби.
Відзначимо найвідомішу інтерпретацію проблеми про
чотири фарби. Нехай є географічна карта. Чи можна,
використовуючи тільки 4 фарби, зобразити цю карту так, щоб
сусідні країни (що мають загальну границю) були
пофарбовані в різні кольори? Зрозуміло, що у відповідному
графі вершинами є країни, а суміжними вершинами є сусідні
країни. Ясно, що отриманий граф є планарним, і після 1976 р.
відповідь на це питання є позитивною.
Замітимо, що в теорії графів ставиться часто питання
про реберне розфарбування графів. Яке мінімальне число
кольорів (це число іноді називають реберно-хроматичним)
потрібно, щоб розфарбувати ребра графа так, що будь-які 2
суміжні ребра (тобто 2 ребра, що мають загальну вершину)
були б пофарбовані в різні кольори? Для реберно-
хроматичного числа графа справедлива теорема.
Теорема Візинга. Якщо в графі максимальний ступінь
вершин дорівнює , то реберно-хроматичне число дорівнює
або , або  +1.
Помітимо, що дотепер відсутні уточнення критеріїв для
графів, коли ж саме реберно-хроматичне число дорівнює , а
коли  + 1.
Очевидно, що найпростіший алгоритм знаходження
реберно-хроматичного числа (і відповідного розфарбування
ребер) полягає в наступному: по даному графі будуємо так
званий двоїстий граф: ребра графа відповідають вершинам
нового (двоїстого) графа, причому, якщо 2 ребра мають
загальну вершину, то вони є суміжними й у двоїстому графі
з'єднані ребром. Після цього розфарбовуємо щонайкраще
вершини двоїстого графа й, переходячи до “старого” графу,
73