Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

Лекция 18. Раскаска графов. Хроматическое число графов Теорема Кенига (2 часа)
План:
1. Раскраска графов
2. Алгоритм последовательной раскраски
3. Раскраска ребер
Ключевые слова: Раскраска графа, хроматическое число, одноцветный класс, цветные классы, реберная k-раскраска, реберное хроматическое число.


1. Раскраска графов
Раскраской графа называется такое приписывание цветов (натуральных чисел) его вершинам, что никакие две смежные вершины не получают одинаковый цвет.
Наименьшее возможное число цветов в раскраске называется хроматическим числом.
Множество вершин одного цвета называется одноцветным классом.
Граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы его ребра не пересекались.
Граф называется планарным, если его можно уложить на плоскости.
Эйлерова характеристика – это соотношения между числом вершин, ребер и граней.
Формула Эйлера: в связном планарном графе справедливо p-q+r=2, где
p - число вершин, q – число ребер, r – число граней плоского графа.
Следствие: если G – связный планарный граф (p>3), то q<=3p – 6.
Следствие: граф планарен тогда и только тогда, когда он не содержит в качестве подграфов ни G1, ни G2.



G1 G2
Следствие: в любом планарном графе существует вершина, степень которой не больше 5.
Теорема о пяти красках: всякий планарный граф можно раскрасить пятью красками.
Связный плоский мультиграф без мостов называется картой.
Мостом называется ребро, при удалении которого увеличивается число компонент графа.
Карта называется к-раскрашиваемой, если для неё существует к-раскраска.
Пусть имеется некоторый граф G неор. и пусть k  натуральное число. Тогда k-раскраской графа G называется произвольная функция f, отображающая множество вершин графа G в некоторое k-элементное множество:
f : VG  {a1, a2, …, ak} = A
В качестве элементов множества A чаще всего используется отрезок натурального ряда {1, 2, …, k} либо {a, b, …, n} или краски типа {синий, красный, …, черный}.
Раскраска называется правильной, если f(u)  f(v) для любых смежных вершин u и v графа G (или концевые вершины любого ребра окрашены в разные цвета).
Г раф, для которого существует правильная k-раскраска, называется k-раскрашиваемым.
Пример.
граф 5-раскрашиваемый
(раскраска правильная)

правильная раскраска

граф 3-раскрашиваемый