DM.III.10

Так же как и число скрещиваний, толщина графа характеризует степень его «непланарности». Толщина планарного графа равна единице, а толщина графов и – двум.

Нижнюю оценку толщины графа дает

Теорема 3.11.9. Пусть – граф, имеющий вершин и ребер. Тогда

, .

Следствие. Для полного графа имеет место равенство .

§12. Раскраска графов

В параграфе рассматриваются основные результаты, связанные с раскраской граней, вершин и ребер графа.

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

В 1852 году лондонский студент Ф.Гутерье обнаружил, что для различения графств на карте Англии достаточно четырех красок. Он высказал гипотезу о том, что любую географическую карту можно правильно раскрасить при помощи четырех цветов. В отечественной литературе появление названной гипотезы иногда связывают с именем английского математика А.Кэли, который в 1879 году высказал ее на заседании Лондонского географического общества, а затем опубликовал в первом томе трудов этого общества.

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

В том, что для раскрашивания графа могут потребоваться, как минимум, краски четырех цветов, легко убедиться с помощью графа, представленного на рис. 160. Этот граф имеет четыре грани, для правильной раскраски которых необходимы 4 цвета. Если бы удалось привести пример графа, для раскраски которого четырех красок недостаточно, то гипотеза Гутерье-Кэли была бы опровергнута. Подтверждение или опровержение этой на первый взгляд простой гипотезы оказалось очень трудной математической задачей, которая получила название «проблема четырех красок». Многие математики и любители математики пытались (иногда в течение многих лет) решить эту проблему. Известно очень много несостоявшихся «доказательств», но нет худа без добра: эти попытки существенно стимулировали становление и развитие теории графов.

Автором одного из таких «доказательств», предложенного уже 1880 году, был А.Кэмп. Однако английский математик П.Дж.Хивуд нашел в нем ошибку и в 1890 году доказал более слабое утверждение: для раскрашивания любой карты достаточно пяти цветов. Существенным продвижением в решении проблемы был результат О.Оре и И.Стемпла, которые в 1968 году доказали, что четырех красок достаточно для раскрашивания карты, содержащей не более 40 стран.

Дальнейшие успехи в решении проблемы четырех красок связаны с использованием ЭВМ. В 1969 году Х.Хееш выделил и четко описал почти 2000 всех возможных типов карт, позднее это число было уменьшено до 1482. В 1976 году группой американских математиков и программистов под руководством К.Аппеля и В.Хакена было анонсировано положительное компьютерное решение рассматриваемой проблемы. С помощью специально разработанных программ, выполнив десятки миллиардов операций, компьютеры позволили разработчикам установить, что ни в одном из выделенных типов карт нет таких карт, которые нельзя раскрасить с помощью четырех красок. Следует заметить, что три типа карт были исследованы «вручную», компьютер с ними не справился. Существенным недостатком полученного решения проблемы, которое не устраивало прежде всего математиков, было то, что все компьютерные вычисления невозможно перепроверить «вручную».

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

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

Уточним понятия карты и ее раскраски на языке теории графов. Пусть задан плоский граф . Говорят, что грани этого графа правильно раскрашены, если каждой грани из F присвоен определенный цвет, причем любым двум смежным граням присвоены разные цвета. Отсюда следует, что если грани графа G правильно раскрашены, то две грани имеющие общее ребро будут иметь разные цвета, а грани имеющие общую вершину, но не имеющие общего ребра, могут быть одноцветными. Очевидно, что одноцветными могут быть также грани, не имеющие общих вершин, а значит, и общих ребер. Наконец, в соответствии с приведенными требованиями в графе, допускающем правильную раскраску граней, могут быть параллельные ребра, но не может быть перешейков. Таким образом, карту можно определить как связный плоский псевдограф, не имеющий перешейков.

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

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

2. Правильная раскраска вершин графа. Оказалось, что задача правильной раскраски карт эквивалентна задаче правильной раскраски вершин плоского графа.

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

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

Наименьшее число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом графа G и обозначается . При граф называется k-хрома-тическим, а его k-раскраска – минимальной.

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

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

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

Обратно, пусть граф является 2-хроматическим и его вершины раскрашены в два цвета  и . Разобьем множество вершин V графа G на два подмножества V_ и V_ в зависимости от их цвета. По определению 2-хроматичности, ни одна вершина из подмножества V_ не может быть смежна ни одной вершине из V_. Следовательно, граф G является двудольным.

Итак, для любого двудольного графа . Это позволяет следующим образом переформулировать рассмотренную ранее теорему Кёнига о двудольных графах:

Связный граф является двудольным тогда и только тогда, когда он является 2-хроматическим,

или

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

Поэтому двудольные графы часто называют бихроматическими.

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

Определение хроматического числа для произвольных графов является достаточно сложной задачей и эффективных алгоритмов ее решения неизвестно. Существуют, однако, простые алгоритмы (например, алгоритм последовательной раскраски [11]), которые приводят к правильным раскраскам, близким к минимальным.

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

Теорема 3.12.1. Пусть граф является объединением связных компонент , тогда

.

Следствие 1. Для несвязного графа , имеющего компоненты , тогда и только тогда, когда для некоторого .

Следствие 2. Если граф является k-хрома-тическим, то k-хроматическим является хотя бы один из графов .

Задача 12.1. Найти число способов раскраски графов и .

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

. (3.12.1)

Ясно, что – функция, зависящая от вида графа , которая удовлетворяет условиям: при и при . Более того, исходя из результатов задачи 12.1, можно предположить, что эта функция является полиномиальной.

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

Т ак, граф на рис. 161 имеет несмежные ребра и , которые соединены ребром в графе и отождествлены в графе .

Теорема 3.12.2. Пусть – простой граф, а и – его несмежные вершины, тогда

. (3.12.2)

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

Следствие. Функция простого графа является полиномиальной.

Многочлен называется хроматическим многочленом (или хроматическим полиномом) графа .

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

О тсюда следует, что

.

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

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

Задача 12.2. В субботу на вечернем отделении факультета информатики должны быть прочитаны часовые лекции по дискретной математике, теории алгоритмов, теории и методике обучения информатике, численным методам, физике и проведен часовой практикум по решению задач на ЭВМ. Некоторые занятия не могут проводиться одновременно по следующим причинам: лекции читает один и тот же преподаватель; преподаватель занят на других курсах; для проведения занятий нужен один и тот же класс с интерактивной доской. Такие занятия отмечены в таблице крестиком. Найдите минимальное время, за которое могут быть проведены все занятия, и число вариантов составления соответствующего расписания.

	Дискретная математика	Теория алгоритмов	Теор. и метод. обуч. инф.	Численные методы	Физика	Практикум
Дискретная математика		+	+	+
Теория алгоритмов	+		+	+	+
Теор. и метод. обуч. инф.	+	+		+	+
Численные методы	+	+	+		+	+
Физика		+	+	+		+
Практикум				+	+

Решение. Построим граф несовместимости занятий (рис. 162). В нем вершины соответствуют проводимым занятиям, и две вершины, соответствующие занятиям, которые провести одновременно невозможно, соединены ребром (вершины обозначены первыми буквами названий учебных предметов.)

П остроенный граф содержит полный подграф (например, с вершинами ДМ, ТА, ТМОИ, ЧМ), вер

шины которого нельзя окрасить менее чем в 4 цвета. Следовательно, , и поэтому все занятия можно провести за четыре часа.

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

Отсюда находим

.

Таким образом, . Следовательно, может быть составлено 48 вариантов расписания.

4. Раскраска граней плоского графа. Вернемся к проблеме раскраски граней графа и, стало быть, раскраски карт. Предварительно рассмотрим две следующие теоремы.

Теорема 3.12.3. Плоский граф не может содержать пять попарно смежных граней^.

Теорема 3.12.4. Задача о правильной раскраске вершин плоского графа G эквивалентна задаче о правильной раскраске граней двойственного графа .

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

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

Теорема 3.11.7. (теорема о пяти красках). Любой связный плоский граф допускает правильную окраску граней в пять цветов.

Теорема 3.12.8*. Любой плоский граф допускает правильную окраску вершин в пять цветов.

5. Раскраска ребер графа. Говорят, что ребра графа правильно раскрашены, если каждому ребру этого графа присвоен определенный цвет, причем любым двум смежным ребрам присвоены разные цвета. Иными словами, если ребра графа правильно раскрашены, то все ребра, инцидентные одной вершине, имеют различные цвета. Ясно, что если граф имеет вершину степени р, то его ребра невозможно правильно раскрасить менее чем р цветами.

Граф называется реберно k-раскрашиваемым, если его ребра можно правильно раскрасить в k цветов. Если граф реберно k-раскрашиваем, но не является (k–1)-раскрашиваемым, то k называется реберно-хроматическим числом (или хроматическим классом, хроматическим индексом) графа и обозначается . Если наибольшая из степеней вершин графа равна , то, очевидно, что .

Найдем реберно-хроматическое число графа, приведенного на рис. 168. Начнем окраску его ребер с одной из вершин наибольшей степени, например с . После выбранной на рисунке раскраски ребро можно раскрасить в цвет 1 или 4; раскрасим его в цвет 1. Далее, последовательно устанавливается, что тогда ребро однозначно раскрашивается в цвет 2, ребро – в цвет 3, ребро – в цвет 4. Следовательно, .