§ 3.5. Раскрашивание графов

В теории графов рассматриваются раскрашивания вершин, рёбер, а для графов, имеющих укладку на какой-либо поверхности (например, для планарных графов), – также раскрашивание граней.

Пусть – граф. Правильным раскрашиванием вершин называется отображение такое, что для любых двух смежных вершин Отображение интерпретируется как раскрашивание вершины в цвет с номером Часто вместо натуральных чисел используют символы обозначающие соответственно красный, синий, жёлтый и т.д. цвет.

Хроматическим числом графа называется наименьшее количество цветов, необходимых для правильного раскрашивания вершин графа

Пусть граф, состоящий из компонент связности Так как компоненты раскрашиваются независимо друг от друга, то имеет место соотношение

(9)

Чтобы вычислить хроматическое число конкретного графа надо не только найти правильную раскраску вершин, но также убедиться в том, что меньшим числом красок обойтись нельзя. Часто это требует значительных усилий.

Для полного графа мы имеем – действительно, так как любые две вершины графа смежны, то при правильной раскраске все вершины должны быть раскрашены в разные цвета.

Упражнение 3.26. Граф получен из графа удалением двух смежных, а граф – двух несмежных рёбер. Вычислить хроматические числа и

Решение. Графы изображены на рисунке 3.35.

Граф содержит подграф, изоморфный (это подграф с вершинами ), поэтому Иными словами, вершины должны быть раскрашены в разные цвета. Вершине можно присвоить такой же цвет, какой имеют или Таким образом,

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

Правильная раскраска графов изображена на рисунке 3.36.

Граф называется бихроматическим, если т.е. если для раскраски вершин нужно не более двух красок.

Конечно, среди бихроматических наибольший интерес представляют графы, у которых так как лишь у графа, не имеющего ни одного ребра. Формула (9) показывает, что бихроматичность графа равносильна бихроматичности каждой его компоненты связности. Оказывается, что бихроматические графы имеют довольно простую характеризацию, которая задается простой теоремой.

Теорема. Следующие условия на граф эквивалентны:

(1) бихроматический;

(2) не имеет циклов нечетной длины;

(3) двудольный.

Проиллюстрируем эту теорему примером. А именно, докажем, что графы при всех являются бихроматическими. Это ясно для графов и правильная раскраска которых изображена на рисунке 3.37.

Для произвольного проведём следующие рассуждения. Пусть и – вершины графа (здесь ). Так как смежные вершины отличаются лишь одной компонентой ( ), то у них Следовательно, для смежных вершин суммы и разной чётности. Таким образом, если раскрасить вершины у которых сумма чётная, в один цвет, а те, у которых нечётная, в другой цвет, то смежные вершины будут раскрашены в разные цвета, а значит, Двудольность графа также ясна: если – множество вершин этого графа, то пусть а Тогда – разбиение множества вершин, причём рёбра могут соединять лишь вершины из разных множеств

Рассмотрим теперь раскладку планарного графа Ввиду соотношения (9) мы можем считать, что – связный граф. Возьмём какую-либо его плоскую укладку. Добавление или удаление висячих вершин (вместе с инцидентными им рёбрами) не изменяет хроматического числа, поэтому будем считать, что висячих вершин нет. Разрешим графу иметь кратные рёбра, но запретим наличие петель. Тогда граф будет представлять собой карту на плоскости.

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

Обозначим количества вершин, рёбер и граней графа соответственно

Из построения графа видно, что каждой грани графа соответствует единственная вершина графа и наоборот. Поэтому Далее, каждое ребро графа пересекает единственное ребро графа что определяет взаимно однозначное соответствие между рёбрами графов и Это означает, что Наконец, так как и то ввиду формулы Эйлера (7) мы получаем равенство Таким образом, мы имеем:

(10)

Заметим, что на рисунок 38а можно смотреть и по-другому. Допустим, у нас есть граф но нет пока графа Тогда из рисунка 38а видно, что если мы будем строить граф, сопряжённый с то получим наш исходный граф Следовательно, свойство графов быть сопряжёнными друг к другу является взаимным, т.е. (при подходящем выборе плоской укладки).

Раскрашивание граней планарного графа определяется аналогично раскрашиванию вершин. А именно, при правильном раскрашивании грани, имеющие общие граничные рёбра, должны быть окрашены в разные цвета (грани, имеющие лишь общую вершину, могут быть окрашены в один цвет).

Переход к сопряжённому графу позволяет раскраску вершин свести к раскраске граней и наоборот.

Л. Эйлер доказал, что для правильной раскраски граней любого планарного графа достаточно пяти красок. Эта теорема известна как теорема о пяти красках.

Теорема (Эйлер). Любая карта на плоскости (или сфере) имеет правильную раскраску не более, чем пятью красками.

Отсюда следует соответствующий результат для раскрашивания вершин.

Теорема. Для любого планарного графа

Ключевым моментом в теореме Эйлера является следующая лемма.

Лемма. Любой граф можно превратить в граф, у которого для всех вершин следующим образом:

1. вершины степени 2 удаляются, а соответствующие рёбра “склеиваются” (см. рис. 3.39);

2. Вершина степени заменяется п-угольником (см. рис. 3.40).

В озникает вопрос: является ли число 5 точной границей хроматических чисел планарных графов? Другими словами, не хватит ли 3 или 4 красок? Граф, для раскраски граней которого не хватит 3 красок, приведён на рисунке 3.41.

Здесь грани 1,2,3,4 граничат каждая с каждой, поэтому должны быть закрашены в разные цвета (океану можно присвоить цвет, в который закрашена 3-я грань). Пример карты, для которой 4 цветов не хватит, а нужно все 5, никто не построил. Доказательство того, что для любой карты достаточно 4 цветов, было опубликовано Хейкеном и Аппелем в 1977 году, однако, с этим доказательством не все математики согласны, так как некоторые варианты было поручено перебрать компьютеру, результаты многочасовой работы которого проверить не представляется возможным.

Перейдём теперь к раскраске рёбер.

Правильной раскраской рёбер графа называется отображение такие, что если рёбра имеют общую вершину. Числа – номера красок. Рёберным хроматическим числом графа называется наименьшее число красок, необходимых для правильной раскраски рёбер графа. Введём ещё одно число, характеризующее граф. А именно, пусть

(11)

Так как рёбра, выходящие из одной вершины, должны быть окрашены в разные цвета, то для любой вершины Отсюда следует, что Следующий замечательный результат показывает, что рёберное хроматическое число очень близко к

Теорема Визинга. Для любого графа имеет место неравенство

(12)

Таким образом, если нам удастся найти раскраску ребер с количеством красок, равным то а если мы докажем, что такой раскраски нет, то

Упражнение 27. Вычислить

Решение. Пусть Тогда Следовательно, Обозначим вершины графа буквами Попробуем раскрасить рёбра в 4 цвета. Рёбра, выходящие из вершины должны быть окрашены в разные цвета допустим, это цвета 1,2,3,4. Напишем номера цветов на рисунке 3.42а.

На ребре написано 3,4 это значит, что его можно окрасить в цвета 3,4, но нельзя в 1,2. Аналогичным образом понимаются записи на рёбрах Так как для ребра цвета 3 и 4 сов ершенно равнозначны, то можно считать, что оно окрашено цветом 3. После этого однозначно окрашиваются рёбра: – 2, – 1 (см. рис. 3.42б). Ребро не может быть окрашено ни одним из цветов 1,2,3,4. Следовательно, раскраска в 4 цвета невозможна. По теореме Визинга получаем, что Правильная раскраска рёбер в 5 цветов изображена на рис. 3.43.