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

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

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

Замечание

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

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

Рассмотрим  кольцо R₄, состоящее из четырех элементов, которые мы обозначим через 0, 1, ω, ω². Операция умножения в этом кольце подчиняется закону ω³ = 1, а операция сложения— следующим правилам: z + z = 0 для каждого z R₄   и 1+ω + ω² = 0.

Поскольку каждый элемент из R₄ является противоположным самому себе, то циклы и кограницы графа G над кольцом R₄ можно рассматривать как цепи в E(G) без указания конкретного ориентанта графа G . Реберные раскраски графа G можно трактовать как всюду ненулевые циклы над R₄ если в качестве цветов использовать ненулевые элементы кольца R₄.

Рассмотрим  следующие теоремы:

Теорема 1. Кубический граф G допускает реберную раскраску тогда и только тогда, когда F(G; 4) > 0.

Теорема 2. Пусть В — бонд графа G, t — реберная раскраска этого графа, п_α, n_β и п_γ — количество ребер бонда В, которые при раскраске t получают цвет α, β и γ соответственно. Тогда числа п_а,, п_β и n_γ имеют одинаковую четность.

Доказательство. Бонд В является носителем кограницы графа G над R₄, все коэффициенты которой равны 1. Эта кограница ортогональна циклу t. Следовательно,

 п_α α + n_ββ + п_γγ = 0.

Учитывая, далее, правила сложения в кольце R₄, получаем утверждение теоремы.

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

Пусть, далее, кубический граф G связен и его бонд В имеет торцевые графы Н и К. Предположим сначала, что |В|=2. Преобразуем Н в кубический граф Н₁ присоединением нового ребра А₁, соединяющего вершины графа Н, являющиеся концами ребер из В. Будем называть Н_{ остаточным графом бонда В, содержащим Н; А₁ назовем пополняющим ребром. Существует, конечно, и второй остаточный граф бонда В, содержащий К.

Пусть теперь |B| = 3. Построим из G новый кубический граф Н₁ заменяя К одной новой вершиной k, инцидентной всем трем ребрам бонда В. Аналогичной заменой графа Н образуем граф К₁. Будем называть Н₁ и К₁ остаточными графами бонда В, содержащими Н и К соответственно.

 

Задачи на графы с  цветными ребрами и вытекающие из них свойства

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

Свойства полных графов с цветными ребрами

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

Решение. Любые два участника турнира находятся между собой в одном из двух отношений: они либо уже сыграли между собой, либо еще не сыграли.

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

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

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