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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ СЕРВИСА»

 

 

 

Кафедра: «Высшая  математика»

 

 

Реферат на тему:

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

по дисциплине

Теория вероятности  и математическая статистика.

 

 

 

 

 

Выполнили

студентки Борискина А.

группа ББИ-101

проверила доц. Спирина  М.С.

 

 

 

Тольятти,2012г.

Введение

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

Первой работой теории графов как  математической дисциплины считают  статью Эйлера (1736г.), в которой рассматривалась  задача о Кёнигсбергских мостах.  Эйлер показал, что нельзя обойти семь городских мостов и вернуться  в исходную точку, пройдя по каждому  мосту  ровно один раз. Следующий  импульс теория графов получила спустя почти 100 лет с  развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

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

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

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

 

 

 

 

 

 

 

1. Основные определения

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

Таким образом, ребро определяется парой вершин. Два ребра, у которых  есть общая вершина, также называются смежными (или соседними).

Граф определяется как  совокупность множества М с заданым на нем бинарным отношениемТМ² .

 

Между элементами М и Т определено отношение инцидентности, т.е. связи между двумя элементами множества М через один элемент множества Т  (рис.1).

Рис.1 пример графа «звезда».

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

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

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

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

Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

Последовательности вершин (рис. 2): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.

Рис.2

Если имеется некоторый маршрут  из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).

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

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

Следующее определение имеет смысл  только для графов или мультиграфов без петель (но не для орграфов).

Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

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

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

 

 

 

 

 

 

 

 

 

 

2. Раскраска графа

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

Пример: 

Правильная раскраска  графа G может выглядеть следующим образом:

Рис.3

Функцией Гранди называется функция на вершинах графа, отображающая вершины в множество {1,2,…, a}, причем если вершина x_i окрашена в цвет с номером k, то функция Гранди h(x_i) = k.

Ясно, что для данного  графа хроматическое число является единственным, но функций Гранди может  быть очень много. Естественно, что  найти хотя бы одну функцию Гранди – это значит, найти одну из возможных  “наилучших” раскрасок (таких раскрасок  может быть много).

Заметим, что если данный граф является полным, т. е. любые две вершины являются смежными, то хроматическое число такого графа равно п, где п – число вершин.

 Алгоритм неявного перебора

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

 

Алгоритм

Предположим, что множество  вершин как-то упорядочено и x_i — i-я вершина этого множества. Тогда первоначальная допустимая раскраска может быть получена так:

1. Окрасить x_i в цвет 1.
2. Каждую из оставшихся вершин окрашивать последовательно: вершина x_i окрашивается в цвет с наименьшим возможным «номером» (т. е. выбираемый цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, смежной x_i).

Данный алгоритм можно  ускорить, используя следующие замечания:

1. При любом упорядочении вершин допустимые цвета j для вершины x_i удовлетворяют условию j≤i.
2. С вычислительной точки зрения выгодно размещать вершины так, чтобы первые вершины образовывали максимальную клику графа. Тогда все вершины, входящие в эту клику будут окрашены в цвет 1 и алгоритм может закончить работу раньше.

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

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

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

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

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

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

В этом простейшем из методов  вершины вначале располагаются  в порядке невозрастания их степеней.

Алгоритм

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

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

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

Также можно изначально упорядочивать  вершины по двухшаговым или трехшаговым степеням.

Теорема. Если максимальная степень вершин в графе равна , то хроматическое число этого графа не превосходит  + 1. При этом хроматическое число графа равно  + 1 только в двух случаях: во-первых, если граф является полным и, во-вторых, если  = 2 и при этом данный граф содержит контур нечетной длины (такой граф изображен на рис. 5, максимальная степень его вершин – 2, а хроматическое число – 3). Во всех остальных случаях хроматическое число графа не превосходит максимальной степени вершин.

 
                                   Рис.4                                                                      Рис.5

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

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

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

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

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

Рис.6

Можно доказать (это не совсем простая теорема), что хроматическое  число планарных графов меньше или  равно 5. Однако Августом де Морганом (1850) была выдвинута гипотеза о том, что  хроматическое число планарных графов меньше или равно 4. Этой проблеме было посвящено огромное число математических работ. В конце концов, удалось свести эту проблему к исследованию верности этой гипотезы для достаточно большого числа типов графов ( 30 тыс.), что и было сделано с помощью компьютеров (1976). Гипотеза о четырех красках оказалась справедливой, а сама проблема перешла в задачу об упрощении доказательства гипотезы о четырех красках.