Оглавление

Введение: 2

Глава I. Вершинная раскраска графа 4

1.1 Основные понятия вершинной раскраски графа. 4

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

Глава II. Реберная раскраска графа 15

2.1 Раскрытие понятия правильной реберной раскраски графа. 15

2.2 Методы реберной раскраски графа 16

Литература 22

     Введение:

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

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

     Пусть S_n — множество целых чисел от 1 до п, которые мы будем называть цветами; n-раскраской графа G назовем такое отображение множества V(G) в S_n, при котором вершины, являющиеся концами одного ребра, окрашиваются в разные цвета (т.е. таким вершинам сопоставляются разные элементы из S_n). Через N(G;n) обозначим число n-раскрасок графа G. Очевидно, что N(G;n) является графовой функцией. Ясно также, что если G имеет петли, то N(G;n)=0.

     Будем считать, что для пустого множества  существует лишь одно его отображение  в S_n. Значит, если G — пустой граф, то полагаем N(G; п)=1.

     Пусть G — объединение непересекающихся графов H и К. Тогда n-раскраска графа G является комбинацией какой-либо n-раскраски графа H и n-раскраски графа К, т. е.

     N (G; п) = N (H; п) N (К; п).

     Пусть граф G имеет звено А с концами х и у. Тогда множество всех n-раскрасок графа G можно отождествить с подмножеством n-раскрасок графа G'_A, у которых вершины х и у окрашены в разные цвета. Далее, рассматривая «сращивание» вершин хиу, заключаем, что множество всех n-раскрасок графа G_A^'' можно отождествить с подмножеством тех л-раскрасок графа G'_a, , в которых вершины х и у окрашиваются в один цвет. Таким образом,

     N(G; n) = N(G'_A; n)-N(;n).

     Существуют  следующие теоремы о раскраски  графа 
 

     Теорема 1:

     Для произвольного графа G и любого положительного целого п число  раскрасок графа G равно Р (G; n).

     Теорема 2:

     Пусть G — граф без петель. Тогда P(G;n)≥0  для всех положительных целых п и при n≥|V (G)| это неравенство является строгим. Если P(G; п) = 0, то и P (G; m) = 0 для положительных целых m < n.

     Первое  утверждение этой теоремы следует  из теоремы 1 и того факта, что при  n≥|V(G)|, приписывая каждой вершине свой цвет, получаем n-раскраску графа G. Для завершения доказательства теоремы заметим, что m-раскраска является и n-раскраской (при m < n).

     На  основании теоремы 1 P(G;λ) можно назвать хроматическим многочленом графа G. Из теоремы 2 следует, что для каждого непустого графа G без петель существует наименьшее положительное целое число n, такое, что граф G имеет n-раскраску. Оно называется хроматическим числом графа G. Граф с хроматическим числом n называется n-хроматическим.

     Результаты, касающиеся проблем раскраски, занимают значительное место в теории графов. Хроматические многочлены представляют интерес для теории графов главным  образом благодаря интерпретации, данной в теореме 1. Исторически начало их изучения связано с рассмотрением  задачи перечисления n-раскрасок. 

Глава I. Вершинная раскраска графа

1.1 Основные понятия  вершинной раскраски  графа.

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

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

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

     Однако  хроматическое число может быть и строго больше кликового числа. Например, для цикла длины 5 , а . Другой пример показан на рис. 10.1. На нем изображен граф, вершины которого раскрашены в 4 цвета (цвета вершин показаны в скобках). Нетрудно проверить, что трех цветов для правильной раскраски этого графа недостаточно. Следовательно, его хроматическое число равно 4. Очевидно также, что кликовое число этого графа равно 3.

      
Рис. 1. 

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

     Для графов с хроматическим числом 3 такого простого описания мы не знаем. Неизвестны и простые алгоритмы, проверяющие, можно ли данный граф раскрасить в 3 цвета. Более того, задача такой  проверки (вообще, задача проверки возможности раскрасить граф в цветов при любом фиксированном ) является NP-полной.

     Делая вывод из выше сказанного приведем несколько определений вершинной раскраски графа: 

     Определение 1:

     Произвольное  отображение f: V(G)→{1,2,…,k} называется вершинной k-раскраской графа G.

     Пример:

     Вершины графа G можно раскрасить следующим способом:

     Определение 2:

     Раскраска называется правильной, если для любых  смежных вершин u,v V(G)  f(u)≠f(v), т.е. никакие смежные вершины не окрашены в один цвет.

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

     Определение 3:

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

     Для графа из предыдущего примера (G)=2, так как использование краски 3 излишне, – эту вершину можно окрасить краской 1.

     Пусть G — простой граф, максимальная валентность  вершин которого равна k. Тогда G допускает (k + 1)- раскраску.

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

     Рассмотрим  теорему Брукса. Пусть G— простой связный граф, максимальная валентность вершин которого равна k>2. Тогда либо G является (k + 1) -кликой, либо он имеет k-раскраску.

     Доказательство. Пусть G — такой граф с наименьшим числом вершин, для которого теорема  не верна. Рассмотрим его (k + 1)-раскраску. Цвета 1, ..., k будем называть обычными, цвет (k + 1) — критическим.

     Существует  так же лемма. Пусть L — цепь графа G с концами х и у. Тогда указанную выше (k + 1) -раскраску графа G можно, изменяя цвета лишь на вершинах из L, преобразовать таким образом, что критический цвет не будет приписан вершинам из L, отличным от х.

     Доказательство. Расположим вершины цепи L в последовательность    (a₀, a₁, a₂ …, a_s) в которой а₀ = у и a_s — x. Перекрасим вершины этой последовательности в соответствии со следующими правилами:

1. вершине а₀ приписывается тот обычный цвет, в который не окрашены смежные с ней вершины, отличные от а₁;
2. перекрасив вершину a_j (0 <j<s - 2), вершине a_j+1 приписываем тот обычный цвет, в который не окрашены смежные с ней вершины, отличные от а_j+2;
3. перекрасив вершину a_s-1 приписываем вершине a_s тот цвет (возможно критический), в который не окрашены смежные с ней вершины.

     Указанный процесс может быть осуществлен  в силу ограничения на валентность  вершин графа G. Это даст требуемую  новую (k + 1) -раскраску. А

     Какова  бы ни была вершина х графа G, можно (достаточное число раз применив лемму описанную выше) построить такую (k + 1)- рас краску графа G, при которой в критический цвет окрашивается только вершина х (отказаться от критического цвета нельзя в силу выбора графа G). Эту раскраску мы назовем критической раскраской графа G с критической вершиной х.

     Теперь  рассмотрим некоторые теоремы связанные  с вершинной раскраской графа

     Теорема 1:

     1)для  любого дерева T  c (T)=2,

     2)для  любого n  c (O_n)=1,

     3)для  любого n c  (K_n)=n,

     4)для  любого n  (C_n)= c      

     Теорема 2 (о пяти красках):

     Если G – планарный граф, то c (G)≤5.

     Доказательство:

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

     Индуктивное предположение: допустим, что для  правильной раскраски всякого плоского графа с числом вершин <k достаточно пяти красок.

     Индуктивный переход: докажем, что для правильной раскраски всякого плоского графа  с числом вершин =k достаточно пяти красок.

     По  следствию 11 из теоремы  Эйлера в плоском графе G существует вершина , степень которой не превосходит 5.

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

     Рассмотрим  случай, когда вершина   смежна в  ровно с пятью вершинами и все они окрашены в разные цвета. Очевидно, что в других случаях (когда степень вершины  меньше 5 или среди окружения есть одноцветные) для правильной раскраски вершины  и ее окружения достаточно 5 красок.

      , где вершина окрашена в цвет i.

     Если  , то инверсируем в A краски (вершины цвета 1 окрашиваем цветом  3, вершины цвета 3 окрашиваем цветом 1). Правильность окраски не нарушилась, а для вершины  освободился цвет 1.

     Если  , то вершина окружена циклом цвета 1,3. Значит, . Произведя в B инверсию окраски, освобождаем для вершины цвет 4.

     Таким образом, граф G раскрашен правильно  красками из фиксированной  правильной окраски графа . Следовательно .

     Количество  способов правильной t-раскраски графа  G называется хроматической функцией. Обозначают .

     Например, .

     Для любого G, если , то f(G, t)=0.

     Для полного графа   
 

     Теорема 3:

     Если , то .

     Доказательство:

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

     Теорема 4:

     Если   и графы  и  имеют ровно одну общую вершину, то .

     Доказательство:

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

     Теорема 5:

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

     Доказательство:

     Рассмотрим  все произвольные раскраски графа  G. Рассмотрим те из них, при которых вершины и  окрашены в разные цвета. Если добавить к графу G ребро , то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых  и  одного цвета. Все эти раскраски останутся правильными и для графа, полученного из G слиянием вершин u и v.

     Замечание

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

     Следствие 1:

     Хроматическая функция любого графа G равна сумме хроматических  функций некоторого числа полных графов, порядки которых  не превосходят порядка  графа G.

     Следствие 2:

     Хроматическая функция любого графа  является полиномом  от t.

     Пример: Найдем хроматический полином  графа G 

     Будем обозначать , если

     Теорема 6:

     Если  граф G порядка n является деревом, то .

     Доказательство:

     Пусть граф является деревом, тогда методом  математической индукции докажем, что  .

     Базис индукции: при n=1 ,  f(T, t)=t; при n=2 ,  
 f(T, t)=t(t–1).

     Индуктивное предположение: пусть условие теоремы  верно при n=k.

     Индуктивный переход: покажем, что условие теоремы  выполняется при n=k+1. Рассмотрим граф . Представим это дерево в виде объединения любого его концевого ребра и дерева порядка k, которое получается, если удалить это концевое ребро из дерева порядка k+1. , причем эти два графа имеют ровно одну общую вершину, поэтому .

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

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

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

     Рис. 2. 

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

Глава II. Реберная раскраска графа

2.1 Раскрытие понятия правильной реберной раскраски графа.

     Наряду  с задачей о раскраске вершин имеется задача о раскраске ребер  графа, когда цвета назначаются  ребрам.

     Пусть G — кубический граф. Рассмотрим множество  Т = = {а, p,v}, элементы которого назовем цветами. Реберной раскраской (или раскраской по Тейту) графа G назовем отображение t множества E(G) в Т, при котором ребра, инцидентные одной и той же вершине, отображаются в три различных цвета. Из определения следует, что граф, содержащий петлю, не допускает реберной раскраски.

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

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

     Для реберной раскраски графа так  же существует ряд теорем

     Теорема 1:

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

     Доказательство:

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

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

2.2 Методы реберной  раскраски графа

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

     Веером  называется подграф  , , состоящий из вершин и ребер , в котором:

• ребро не окрашено;
• ребро окрашено в цвет , ;
• в вершине отсутствует цвет , ;
• все попарно различны.

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

      
Рис. 3. 

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

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

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

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

      Рис. 4

     Рассмотрим  две возможности:

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

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

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

      
Рис. 5. 

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