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

Под раскраской вершин графа понимается процедура приписывания цветов (меток) вершинам графа G(X,V).

Правильной раскраской графа в k цветов (k-раскраской графа) считается такая раскраска вершин графа G(X,V), при которой никакие две смежные вершины не получают одинакового цвета. При этом множество вершин графа разбивается на цветные класс, каждый из которых объединяет вершины одного цвета.

Пример 5.11. Рассмотрим граф, представленный на рис. 45.

Множество вершин графа {1,2,3,4,5}. Множество цветов{A,B}. Правильная раскраска: {(1,A), (2,B), (3,A), (4,B), (5,A)}. Цветные классы: {1,3,5}и{2,4}

Задача о раскраске вершин состоит в нахождении правильной раскраски вершин графа G в наименьшее число цветов. Это число называется хроматическим числом графа G (обозначается X(G)). При этом если χ(G) = k, то граф G называется k–хроматическим.

Общего решения задачи о раскраске вершин не найдено, установлены только верхние границы.

Теорема 1. Если максимальная степень вершин в графе равна p ≥ 3, то хроматическое число этого графа не превосходит p+1

Отметим, что хроматическое число графа равно p+1 только в двух случаях: если граф является полным (в этом случае хроматическое число полного графа равно χ(K_n)= n) и, если p = 2 и данный граф представляет собой контур нечетной длины, максимальная степень вершин которого равна 2, а хроматическое число – 3. Во всех остальных случаях хроматическое число графа не превосходит максимальной степени вершин. Для дерева χ(D) = 2.

Граф, хроматическое число которого равно 2, называется бихроматическим.

Теорема Кенига (необходимое и достаточное условие бихроматичности графа). Для того, чтобы простой связный граф был бихроматическим, необходимо и достаточно, чтобы он не содержал циклов нечетной длины.

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

Пример 5.12. Найти хроматическое число графа G (рис. 46).

Выпишем последовательность вершин графа в порядке невозрастания их степеней

v₁, v₃, v₄, v₈, v₅, v₆, v₂, v₇.

Раскрасим вершины из списка следующим образом: v₁ в цвет A, v₃ в цвет B, v₄ в цвет C, v₈ в цвет A, v₅ в цвет B, v₆ в цвет C, v₂ в цвет C, v₇ в цвет B. При раскраске вершин мы использовали 3 цвета, поэтому χ(G) )=3.

Проблема раскраски планарных графов является одной из самых знаменитых проблем теории графов (проблемой четырех красок). Граф называется плоским, если он нарисован на плоскости, причем любые 2 ребра могут пересекаться только в вершине. Граф называется планарным, если он изоморфен плоскому графу. Таким образом, планарный граф можно изобразить на плоскости как плоский. На рис. 47 изображены 2 изоморфных (одинаковых) графа, причем первый из них планарный, а второй является плоским.

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

В 1879 г. английский математик Кэли сформулировал гипотезу четырех красок: «Всякий планарный граф 4-раскрашиваем».

Попытки доказать эту гипотезу привели к 1890 г. к появлению следующей теоремы.

Теорема Хивуда. Всякий планарный граф 5- раскрашиваем. В 1976 г. американские математики К. Аппель и В. Хейкен доказали гипотезу четырех красок, существенно используя при этом компьютерные вычисления (сложным и трудно воспроизводимым способом).

Раскраска вершин графа в J цвета есть разбиение множества вершин графа на попарно непересекающиеся непустые подмножества, состоящие из попарно несмежных вершин.

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

П ример 5.13. У графа (рис. 48) имеется 3 максимально независимых систем вершин: {5}, {1,3} и {2,4}. Ясно, что при любой процедуре нахождения хроматического числа в этом графе, получим число 3.

Рассмотрим алгоритм нахождения наилучшей раскраски вершин графа. Найдем в графе G какую-либо МНС, которую обозначим S₁, и все вершины, входящие в эту МНС, окрасим в цвет № 1. Удалим из данного графа все вершины, входящие в эту МНС (вместе с ребрами), и для нового графа снова найдем МНС, которую обозначим S₂. Эти новые вершины окрасим в цвет № 2, затем удалим эти вершины из графа вместе с соответствующими ребрами. Снова находим МНС, которую окрасим в цвет № 3, и т. д.

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

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

.

Решение. Для графа G, моделирующего отношения между отдыхающими (рис. 49), разбиение выявило наличие двух МНС

Пример 5.15. На предприятии планируется выполнить 8 работ: v₁,v₂,…v₈. Для выполнения этих работ необходимы механизмы а₁,а₂,…,а₆. Использование механизмов для проведения каждой из работ определяется следующей таблицей:

Таблица 32

	v1	v2	v3	v4	v5	v6	v7
а1	+		+				+
a2		+		+
a3			+			+	+
a4	+	+		+	+
a5			+		+
a6					+	+

Никакой из механизмов не может быть занят одновременно на двух работах. Все работы выполняются за одно и тоже время t. Требуется распределить механизмы так, чтобы суммарное время выполнения всех работ было наименьшим.

Р

v₁

ешение. Рассмотрим граф G, множество вершин V которого состоит из планируемых работ, т.е. V={v₁,v₂,…,v₈}. Вершины v_i и v_j соединим ребром в том и только в том случае, когда существует хотя бы один механизм, который используется при выполнении и той и другой работы. Получим граф, изображенный на рис. 50.

v₂

v₈

v₃

v₇

v₄

v₆

v₅

Рис. 50

Граф содержит четырехэлементный полный подграф {v₁,v₂,v₄,v₅}, поэтому для правильной раскраски графа потребуется, как минимум четыре краски (красная, синяя, зеленая, желтая), как показано на рис. 50. Вершины v₃ и v₈ смежны между собой и смежны вершинам v1 и v5, раскрашенным первой (красной) и четвертой (желтой) красками, поэтому для них остаются синяя и зеленая краска. Осталось раскрасить вершины v₆ и v₇. Вершину v₆ красим первой (красной), а v₇ – четвертой (желтой) красками. Хроматическое число графа равно 4. Следовательно, все работы можно выполнить за время 4t. Сначала можно выполнить работы v₁ и v₆, затем v₂ и v₈, потом v₃ и v₄ и, наконец, v₅ и v₇.