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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования «Чувашский государственный университет имени И.Н.Ульянова» АЛАТЫРСКИЙ ФИЛИАЛ Факультет управления и экономики  Кафедра Высшей математики и информационных технологий     КУРСОВАЯ РАБОТА по дисциплине: «Дискретная математика» на тему: «Раскраски графов»                                                                                        Выполнил студент                                                               1 курса                                                               группы                                                                                                     Научный руководитель:           2009

 

 

Содержание

Стр.

Введение                                                                                                          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. Переборный алгоритм для раскраски

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