СDМ L 7.4

1.

Комп'ютерна дискретна математика
МОДУЛЬ 7. Теорія графів
Лекція 4. Розфарбування графів
Трунова Олена Василівна
доцент, к. пед. н.

2. План

1.Хроматичне число графу
2.Розфарбування вершин графу
3.Розфарбування ребер графу
4.Прикладні задачі, що зв’язані з розфарбуваннями

3.

У 1852 році Френсіс Гутрі (Guthrie), складаючи карту графств Англії, звернув
увагу, що для її повного розфарбування вистачить чотирьох кольорів, тоді
два сусідні графства на географічній карті будуть розфарбовані різними
кольорами. Його брат, Фредрік, сповістив про це відомому математику О.
Де Моргану (DeMorgan), а той – математичній громадськості. Точне
формулювання гіпотези опублікував А. Келі (Cayley) у 1878 році. Так
з’явилася гіпотеза про чотири фарби. Вона буде розглянута трохи пізніше
Рисунок 1 – Френсіс Гутрі
Рисунок 2 – О. Де Моргану
Рисунок 3 – А. Келі

4.

Нехай існує деякий граф G з n вершинами, які треба розфарбувати.
Нехай існує деяке число фарб