lign="justify">     

     

     

     Если  , то инверсируем в 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, за полиномиальное время находит раскраску в не более чем цветов. Его можно назвать "идеальным" приближенным алгоритмом - более высокую точность имеет только точный алгоритм.