Урок Раскраски графов (9 класс)

Урок «Раскраски графов»

факультативного курса «теория графов и их приложения» (9 класс)

Одной из наиболее интересных задач теории графов, с которой необходимо знакомить школьников, является задача о раскрасках вершин графа. На практике к этой задаче сводятся такие проблемы как составление расписаний занятий в учебном заведении, распределение оборудования на предприятии, выбор расцветки проводов при монтаже электрооборудования автомобиля и многие другие. Классической задачей о раскраске графа, с помощью которой хорошо демонстрируется суть проблемы, является задача о раскраске политической карты мира. Имеется карта мира, с нанесенными границами между государствами (фрагмент такой карты представлен на рис. 1, для удобства цвета обозначены буквами: Ж - желтый, С - сиреневый, З - зеленый). Каждое государство необходимо раскрасить в определенный цвет так, чтобы граничащие с ним государства были окрашены в различные цвета - для того, чтобы они были хорошо заметны на карте. Количество используемых красок для раскраски всей карты должно быть минимальным. Очевидно, что при такой постановке проблемы государства, не граничащие между собой, могут быть окрашены в один и тот же цвет (рис. 1,б).

Рис. 1. Фрагмент политической карты мира (а - не раскрашенный, б - раскрашенный)

Представим карту посредством графа (рис. 2). Таким образом, раскраской вершин неориентированного графа G называется такое задание цветов вершинам, что если - ребро, то вершины v₁ и v₂ имеют различные цвета (рис. 2,б). Такую раскраску называют правильной.

Рис. 2. Представление карты (а) графом (б)

Минимальное число цветов, требующихся для раскраски графа, называют хроматическим числом. Обычно его обозначают χ(G).

Возникает вопрос, а сколько существует способов раскраски графа при определенном наборе красок? На этот вопрос дает ответ хроматический полином графа. Русский синоним слову полином - многочлен. Если в это математическое выражение подставить число красок, то можно легко вычислить количество способов раскраски. Но сложность состоит в составлении хроматического полинома. Довольно легко хроматический полином определяется для пустых и полных графов. Напомним, что пустым графом (его обозначают O_n) называется граф, не имеющий ни одного ребра - в нем есть только вершины (рис. 3,а). Полный же граф (его обозначают K_n) наоборот, имеет связи между всеми вершинами - они соединены ребрами друг с другом (рис. 3,б)

Рис. 3. Пустой (а) граф O₅ и полный (б) граф K₅

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

,

(1)

где x - число цветов, а n - число вершин графа.

Сложнее с полными графами - все их вершины могут быть раскрашены только в различные цвета, но и здесь число различных комбинаций довольно велико. Эта формула и все дальнейшие утверждения здесь будут приведены без выводов и доказательств - они довольно сложны и заинтересованный читатель может ознакомиться с ними самостоятельно в специальной литературе. Итак, хроматический полином полного графа определяется как (2):

(2)

Такое выражение иногда называют факториальной степенью числа.

Возникает вопрос, а как же быть с графами, которые не являются полными или пустыми? Есть ли какие-нибудь методы получения их хроматических полином? На этот вопрос следует ответить утвердительно - такие методы есть. Одним из таких методов, который базируется на знании хроматических полином для пустых и полных графов является метод хроматической редукции. В данном случае слово редукция означает приведение сложного к простому, или разложение сложного на простые части. Как нетрудно догадаться для получения хроматического полинома графа, нам необходимо будет свести его к сумме (или разности) полиномов пустых или полных графов.

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

Утверждение, являющееся основой для хроматической редукции по полным графам, звучит так: хроматический полином графа может быть представлен суммой хроматических полиномов двух графов и имеет вид (3):

(3)

где G₁ - граф, полученный из графа G добавлением нового ребра (v₁, v₂), а граф G₂ получается из графа G отождествлением вершин v₁ и v₂.

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

(4)

где G₁ - граф, полученный из графа G удалением ребра (v₁, v₂), а граф G₂ получается из графа G отождествлением вершин v₁ и v₂.

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

Рис. 4. Исходный граф (а), добавление (б) в него ребра (v₁, v₃), удаление (г) из него ребра (v₁, v₂), отождествление вершин v₁ и v₃ (г)

Докажем первое утверждение (о редукции по полным графам). Число правильных раскрасок графа G в x цветов, при которых при которых цвета вершин v₁ и v₂ различны, не изменится, если к G присоединить ребро (v₁, v₂), поэтому оно равно P(G₁, x). Аналогично, число правильных раскрасок графа G в x цветов, при которых цвета вершин v₁ и v₂ совпадают, равно P(G₂, x). Сложив эти два числа, получим число правильных раскрасок графа G в x цветов.

Пользуясь представленными выше утверждениями, попытаемся вывести хроматический полином P(G,x) графа G, представленного на рис. 5. Мы будем пользоваться хроматической редукцией по полным графам, то есть будем сводить хроматический полином представленного графа к хроматическим полиномам полных графов.

Рис. 5. Граф с тремя вершинами

Эта задача может быть решена на один шаг. Покажем редукцию по полным графам с помощью рис. 6. Для этого представим исходных граф в виде двух графов - для первого в исходном графе необходимо добавить недостающее ребро (v₁, v₃), а во втором отождествим вершины v₁ и v₃.

Рис. 6. Редукция графа с тремя вершинами

Оба полученных графа являются полными: первый - граф K₃, второй - граф K₂ и редукцию можно прекратить. То есть хроматический полином нашего исходного графа (рис.7) раскладывается на сумму двух хроматических полиномов (5):

(5)

Хроматические полиномы полных графов равны (6)

(6)

Сложив полиномы и приведя подобные, получим (7):

(7)

С помощью хроматического полинома можно найти хроматическое число. Для этого нужно в полином последовательно подставлять числа x=1, 2, 3, … и первое число, при котором полином будет отличаться от нуля и будет хроматическим числом. Для нашего примера хроматическое число равно 2. Это и есть количество способов раскраски данного графа. Оба способа раскраски для двух красок, черной и белой, представлены на рис. 7.

Рис. 7. Варианты раскраски для графа с тремя вершинами при использовании двух цветов (черного и белого)

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

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

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

Покажем работу этого алгоритма на примере. Пусть дан граф, вершины которого надо раскрасить (рис. 8,а). Построим список вершин по убыванию степеней: степень 3 (deg=3) имеют вершины v₁ и v_4; степень 2 (deg=2) имеют вершины v₂, v₃ и v₅.

Рис. 8. Процесс раскраски графа

Выберем вершину с наибольшей степенью, например, v₁ и окрасим ее (рис. 8,б). Мы выбрали в качестве первого цвета синий (С). Вершины, смежные с вершиной v₁, а это вершины v₂, v₄ и v₅ не могут быть окрашены в синий цвет. Ищем вершины, которые можно окрасить в синий цвет. Это единственная вершина v₃. Окрашиваем ее в синий цвет (рис. 8,в). Синий цвет исчерпан, в него нельзя больше окрасить ни одну вершину. Выбираем из списка нераскрашенных вершин вторую вершину с максимальной степенью - это вершина v₄ и окрашиваем ее во второй цвет (рис. 8 г). Пусть это будет красный (К) цвет. Из оставшихся не раскрашенными вершин, вершина v₅ не может быть раскрашена в красный цвет. Ищем вершины, которые можно окрасить в красный. Это единственная вершина v₂. Раскрасим ее в красный. Красный цвет исчерпан. Выбираем единственную не раскрашенную вершину v₅ и раскрашиваем ее в третий цвет - зеленый (З). На этом раскраска графа завершена. Количество используемых красок 3.

В качестве практической и самостоятельной работы следует рекомендовать решение задач, изложенных в пособиях О.И.Мельникова [4, с.20-23, задачи 93-101], [5, с.139-152 , задачи 176-188]. Там же можно найти подробно изложенное решение задач. При решении задач могут использоваться и специализированные математические пакеты, например, такие как Maple или Scilab [6].

Рекомендуемая литература:

1. Березина Л. Ю. Графы и их применение: Пособие для учителей с ил. - М.: Просвещение, 1979. - 143 с.

2. Мельников О.И. Занимательные задачи по теории графов. - Минск: ТетраСистемс, 2001. - 144 с.

3. Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. - М.: Книжный дом «ЛИБРОКОМ», 2009. - 232 с.