Раскраски графов

Содержание

Стр.

Введение                                                                                                          3

1.Теоремы и оценки, относящиеся к хроматическим числам 

     1.1Нижние  оценки для  .                                                       5

     1.2. Верхние оценки для .                                                           5

     1.3. Гипотеза четырех красок.                                                          6

2. Приближенные алгоритмы  раскрашивания.

      2.1. Переборный алгоритм для раскраски                                     9

      2.2. Раскраска ребер                                                                       11

      2.3. Рационализация поиска наибольшего независимого множества                                                                                             15

3. Задачи раскраски.

      3.1. Простая задача размещения (загрузки).                                   17

      3.2. Составление графиков осмотра (проверки).                           18

      3.3. Распределение ресурсов.                                                              18

Заключение                                                                                                   19

Список литературы                                                                                      21

Введение

Разнообразные задачи, возникающие при планировании производства, составлении графиков осмотра, хранения и транспортировке товаров и т.д., могут быть представлены часто как задачи теории графов, тесно связанные с так называемой «задании раскраски». Графы, рассматриваемые в этой главе, являются неориентированными и не имеют петель; если специально не оговаривается иное, то под словом «граф» понимается именно такой граф.

Граф называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G и обозначается . Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.

Вообще говоря, хроматическое число графа (так же как числа независимости и доминирования, рассмотренные в предшествующей главе) нельзя найти, зная только числа вершин и ребер графа. Недостаточно также знать степень каждой вершины, чтобы вычислить хроматическое число графа. В этом можно убедиться, рассматривая графы, приведенные на рис.1(а) и рис.1(б). Эти графы имеют по n=12 вершин, m=16 ребер и одинаковое распределения степенен вершин . Однако хроматические числа данных графов равны 4 и 2 соответственно. При известных величинах n (число вершин), m (число ребер) и (степени вершин графа) можно получить верхнюю и нижнюю оценки для хроматического числа графа. Этим оценкам посвящен следующий раздел.

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

Рис.1. Два графа с одинаковыми  n, m и распределениями степеней вершин, но с различными хроматическими числами. (а) . (б) .

1. Теоремы и оценки, относящиеся к хроматическим числам

1.1. Нижние оценки для .

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

,                                             (1)

где n — число вершин  графа G, а обозначает наибольшее целое число, не превосходящее числа x.

Еще одна нижняя оценка для предложена Геллером:

.                                             (2)

1.2. Верхние оценки для .

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

                                        (3)

1.3. Гипотеза четырех красок.

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

Теорема о пяти красках.

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

«Теорема» о четырех красках (недоказанная).

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

           Теорема (об оптимальной раскраске)

Если граф G является r-хроматическим, то он может быть раскрашен с использованием r (или меньшего числа) красок с помощью следующей процедуры: сначала в один цвет окрашивается некоторое максимальное независимое множество S(G), затем окрашивается в следующий цвет множество S(X\S(G)) и так далее до тех пор, пока не будут раскрашены все вершины.

Доказательство. Тот факт, что такая раскраска, использующая только r цветов, всегда существует, может быть установлен следующим образом. Пусть существует раскраска в r цветов, такая, что одно или больше множеств, окрашенных в один и тот же цвет, не являются максимальными независимыми множествами в смысле, упомянутом выше. Перенумеруем цвета произвольным способом. Очевидно, что мы можем всегда покрасить в цвет 1 те вершины (пусть это множество Vi′), которые не были окрашены в этот цвет и которые образуют максимальное независимое множество вместе с множеством Vi всех вершин графа, уже окрашенных в цвет 1. Эта новая раскраска возможна потому, что никакая вершина из множества Vi′ не является смежной ни с какой вершиной из Vi′ и, следовательно, всякая вершина, которая смежна хотя бы с одной вершиной из Vi′, окрашена в цвет, отличный от цвета 1, и поэтому не затрагивается процедурой перемены цвета вершин из Vi′. Рассматривая теперь подграф (X − Vi′) и проводя с ним аналогичные манипуляции, мы окрасим в цвет 2 какое-то (новое) максимальное независимое множество и т. д.

С помощью процедуры, описанной в этой теореме можно получить раскраску с минимальным количеством цветов для данного графа. Такая раскраска называется оптимальной независимой раскраской.

2. Приближенные алгоритмы раскрашивания.

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

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

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

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

Можно действовать иначе: размещать вершины сразу в соответствии с их степенями или степенями и применять тот же самый последовательный метод раскраски. Таким образом, описанный выше метод раскрашивания очерчивает целый класс последовательных методов, каждый из которых связан с определенным способом упорядочивания вершин, либо статическим, т.е. фиксированным сразу для всей процедуры, либо динамическим, т.е. изменяющимся в процессе раскраски. Способ упорядочивания может базироваться на многих возможных критериях, зависящих от степеней вершин или от каких-либо других родственных характеристик. Результаты вычислении и сравнение последовательных методов раскрашивания для графов, выбранных случайным образом, приведены в работах Матулы, Марбле и Исааксона и Вильямса. Границы применимости этих эвристических методов демонстрируются у Митчема, показавшего, что можно построить графы, для которых любой из эвристических методов дает произвольно плохие оценки хроматического числа.

2.1. Переборный алгоритм для раскраски

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

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

 
Рис. 1. 

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

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

2.2. Раскраска ребер

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

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

Теорема 1. Для любого графа справедливы неравенства .

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

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

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

• ребро не окрашено;

• ребро окрашено в цвет , ;

• в вершине отсутствует цвет , ;

• все попарно различны.

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

 
Рис. 2. 

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

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

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

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

(Б1) Вершины  и принадлежат разным -компонентам. Перекрасим веер . Ребро станет неокрашенным. Теперь перекрасим -компоненту, содержащую вершину . После этого цвет будет отсутствовать в вершине и ребро можно окрасить в этот цвет.

(Б2) Вершины  и принадлежат разным -компонентам. Перекрасим веер . Ребро станет неокрашенным. Теперь перекрасим -компоненту, содержащую вершину . После этого цвет будет отсутствовать в вершине и ребро можно окрасить в этот цвет.

Итак, в любом случае получаем правильную раскраску, в которой добавилось еще одно раскрашенное ребро .

На рис. 3 иллюстрируются случаи (Б1) и (Б2) на примере веера из рисунка 2. Здесь , . Левое изображение соответствует случаю (Б1): вершины и принадлежат разным -компонентам. После перекраски веера и -компоненты, содержащей вершину , появляется возможность окрасить ребро в цвет 5. Случай (Б2) показан справа: здесь вершины и принадлежат разным -компонентам, поэтому после перекраски веера , , , , и -компоненты, содержащей вершину , появляется возможность окрасить ребро в цвет 5.

 
Рис. 3. 

Итак, все графы делятся на два класса: у одних хроматический индекс равен максимальной степени вершины, у других он на единицу больше. Оказывается, определение принадлежности графа к тому или иному классу является NP-трудной задачей. Алгоритм, который можно извлечь из доказательства теоремы 3.2, за полиномиальное время находит раскраску в не более чем цветов. Его можно назвать "идеальным" приближенным алгоритмом - более высокую точность имеет только точный алгоритм.

5. Рационализация поиска наибольшего независимого множества

Известны различные приемы сокращения перебора при использовании описанной стратегии исчерпывающего поиска. Один из них основан на следующем наблюдении. Допустим, в графе , для которого нужно найти наибольшее независимое множество, имеются две вершины и , такие, что каждая вершина, отличная от и смежная с вершиной , смежна и с вершиной . Иначе говоря, . Будем говорить в этом случае, что вершина поглощает вершину . Если при этом вершины и смежны, то скажем, что вершина смежно поглощает вершину . Вершину в этом случае назовем смежно поглощающей. Например, в графе, изображенном на рис. 4, вершина 2 смежно поглощает вершины 1 и 3. Вершины 5 и 6 в этом графе тоже являются смежно поглощающими.

 
Рис. 4. 

Теорема 1. Если вершина является смежно поглощающей в графе , то .

Доказательство. Допустим, вершина смежно поглощает вершину в графе . Пусть - наибольшее независимое множество графа . Если не содержит вершину , то оно является наибольшим независимым множеством и в графе , так что в этом случае . Предположим, что множество содержит вершину . Тогда ни одна вершина из множества не принадлежит . Значит, не содержит вершину и ни одну вершину из множества . Но тогда множество тоже будет независимым, причем оно целиком содержится в графе , а число элементов в нем такое же, как в множестве . Значит, и в этом случае .

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

3. Задачи раскраски.

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

3.1. Простая задача размещения (загрузки).

Рассмотрим задачу размещения (загрузки) n каких-то предметов по ящикам. Пусть каждый предмет соответствует определенной вершине графа G. Всякий раз, когда два предмета и не могут быть размещены в одном ящике (например, когда предмет может загрязнить предмет ), в граф G вводится ребро . Если ящики имеют неограниченную вместимость, так что в каждый из них можно поместить сколько угодно предметов, то задача нахождения наименьшего числа ящиков для размещения предметов эквивалентна задаче нахождения хроматического числа графа G; причем каждому ящику соответствует определенный «цвет», а предметы, окрашенные в один цвет, укладываются в один и тот же ящик.

3.2. Составление графиков осмотра (проверки).

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

3.3. Распределение ресурсов.

Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов . Построим граф G: каждой работе соответствует определенная вершина графа, а ребро существует в графе тогда и только тогда, когда для выполнения i-й и j-й работ требуется  хотя бы один общий  ресурс, т. е. когда  . Это означает, что i-я и j-я работы не могут выполняться одновременно. Раскраска графа G определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цвета, выполняются одновременно. Наилучшее использование ресурсов (т.е. выполнение всех n работ за наименьшие время) достигается при оптимальной раскраске вершин графа G.

Заключение

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

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