2.7. Задачи о раскрасках графа.

На самом деле, это серьезные математические проблемы, так как расскарсить граф в N цветов – это то де самое, что присвоить его вершинам (ребрам) индексы от 1 до n, означающих номер цвета.

= неправильная раскраска.

О раскраске вершин орграфа.

Опр. Граф допускает правильную n-цветную раскраску вершин, если можно раскрасить вершины в n цветов так, что никакие 2 смежные вершины не окрашены одним цветом.

- правильно

Опр. Наименьшим числом n, при котором существует раскраска данного графа называется его хроматическим числом.

Проблема в том, что для любого графа найти его хроматическое число.

Некоторые легкие результаты

1)Полный граф с n вершинами имеет хроматическое число n.

n=5

2) Связный граф, не имеющий циклов(дерево), имеет хроматическое число 2. (можно раскрасить в 2 цвета).

Результат, близкий к полному решению проблемы:

Теорема Брукса (1941)

Если максимальная степень вершины графа равна d, то его хроматическое число h_b≤d+1.

Однако, h_b=d+1, только в 2 случаях

1)Граф является полным.

2)d=2. И при этом граф содержит цикл нечетной длины.

Цикл длины – 5

d=2 h_b=3

В остальных случаях неравенство усиливается h_b≤d.

Алгоритм решения задачи по раскраске вершин графа.

1)Вычислить степени свободы всех вершин в порядке убывания степеней. Присвоить n=1,

2)Окрасить первую неокрашенную вершину в цвет №1.

3)Окрасить в цвет № n все вершины, которые не смежным вершинам, уже окрашенным в цвет № n/

4)Если все вершины уже окрашены, то h_b=n, иначе n:=n+1 и возвращаемся к шагу №2.

Отметим, что на шаге №3 мы перекрашиваем часть вершин.

Еще в 19 веке было замечено, что для любого плоскгого графа удается правильно раскрасить его не более чем в 4 цвета.

Однако, доказать это в общем случае не удавалось более 100 лет. Только в 1989 немецкие математики Аппель и Хамен смогли получить доказательство. Доказательство содержит более 100 страниц и его проверяли несколько лет.

О раскраске ребер графа.

Опр. Правильная раскраска ребер графа такая, что напоминает 2 инцидентные ребра (имеющие одну общую вершину) не окрашены в один цвет.

Минимальное число цветов, необходимое для правильной раскраски ребер, называется хроматическим индексом и обозначается h_p.

Обозначим через d максимальную степень вершин графа. Ясно, что все ребра, инцидентные одной вершине, должны иметь разные цвета.

Откуда ясно, что h_p ≥ d.

Основной результат доказан в 1946г. В.Г.Визингом (г. Одесса)

Для любого графа верно двойное неравенство

d≤h_p≤d+1.

То есть либо h_p=d, либо h_p=d+1

Идея доказательства представляет собой алгоритм правильной раскраски ребер в наименьшие количество цветов( не более d+1). Оно основано на 2 операциях перекрашивания ребер. Встречаются оба случая h_p=d и hp=d+1

Пример

d=2

h_p=2

h_p=d

d=2

h_p=2

h_p=d+1

Вопросы к экзамену

12) Что такое граф, орграф. Вершина графов, дуга, ребро, путь, цепь, контур, цикл.

13)Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе?

14)Каков алгоритм решения задачи о кратчайшем пути во взвешенном графе?

15)Что такое Эйлерова цепь (цикл), у каких графов они существуют?

16) В чем состоит формула Эйлера и для каких объектов она верна?

17) Как выглядит не планарные графа №1 и №2, типов 1 и 2, в чем состоит теорема Куратовского-Понтрягина?

18)Что такое хроматическое число графа и что вы знаете о его величине?

19) Что такое хроматический индекс графа и что вы знаете о его длине.

Задачи могут быть к вопросам 13-15, 17-19.