Графы и алгоритмы

Раскраски

Разбить на страницы
Показывать лекцию целиком

Раскраска вершин

Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа $$1, 2\ldots k$$. Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве $$\{ 1,2\ldots k\}$$. Раскраску можно также рассматривать как разбиение множества вершин $$V=V_{1} \cup V_{2} \cup \ldots \cup V_{k}$$, где $$V_{i}$$ - множество вершин цвета $$i$$. Множества $$V_{i}$$ называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа $$G$$ в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается $$\chi(G)$$.

В правильной раскраске полного графа $$K_{n}$$ все вершины должны иметь разные цвета, поэтому $$\chi (K_{n} )=n$$. Если в каком-нибудь графе имеется полный подграф с $$k$$ вершинами, то для раскраски этого подграфа необходимо $$k$$ цветов. Отсюда следует, что для любого графа выполняется неравенство

$$\chi(G)\ge \omega (G).$$

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

(рис 10.1)

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

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

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

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

Выберем в данном графе $$G$$ две несмежные вершины $$x$$ и $$y$$ и построим два новых графа: $$G_{1}$$, получающийся добавлением ребра $$(x,y)$$ к графу $$G$$, и $$G_{2}$$, получающийся из $$G$$ слиянием вершин $$x$$ и $$y$$. Операция слияния состоит в удалении вершин $$x$$ и $$y$$ и добавлении новой вершины $$z$$ и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин $$x$$, $$y$$. На рис. 10.2 показаны графы $$G_{1}$$ и $$G_{2}$$, получающиеся из графа $$G$$, изображенного на рис. 10.1, с помощью этих операций, если в качестве $$x$$ и $$y$$ взять вершины $$a$$ и $$f$$.

(рис 10.2)

Если в правильной раскраске графа $$G$$ вершины $$x$$ и $$y$$ имеют разные цвета, то она будет правильной и для графа $$G_{1}$$. Если же цвета вершин $$x$$ и $$y$$ в раскраске графа $$G$$ одинаковы, то граф $$G_{2}$$ можно раскрасить в то же число цветов: новая вершина $$z$$ окрашивается в тот цвет, в который окрашены вершины $$x$$ и $$y$$, а все остальные вершины сохраняют те цвета, которые они имели в графе $$G$$. И наоборот, раскраска каждого из графов $$G_{1}$$, $$G_{2}$$, очевидно, дает раскраску графа $$G$$ в то же число цветов. Поэтому

$$\chi (G)=\min \{ \chi (G_{1}),\chi (G_{2})\},$$

что дает возможность рекурсивного нахождения раскраски графа в минимальное число цветов. Заметим, что граф $$G_{1}$$ имеет столько же вершин, сколько исходный граф, но у него больше ребер. Поэтому рекурсия в конечном счете приводит к полным графам, для которых задача о раскраске решается тривиально.

Раскраска ребер

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

Обозначим через $$\Delta (G)$$ максимальную степень вершины в графе. При правильной реберной раскраске все ребра, инцидентные одной вершине, должны иметь разные цвета. Отсюда следует, что для любого графа выполняется неравенство $$\chi'(G)\ge \Delta (G)$$. Для некоторых графов имеет место строгое неравенство, например, $$\Delta (C_{3} )=2$$, а $$\chi'(C_{3} )=3$$. Следующая теорема, доказанная В.Г.Визингом в 1964 г., показывает, что $$\chi'(G)$$ может отличаться от $$\Delta(G)$$ не более чем на 1.

Теорема 1. Для любого графа $$G$$ справедливы неравенства $${\Delta (G)\le \chi'(G)\le \Delta (G)+1}$$.

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

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

Другая операция применяется к частично раскрашенному подграфу, называемому веером. Будем говорить, что при данной раскраске цвет $$\alpha$$ отсутствует в вершине $$x$$, если ни одно из ребер, инцидентных вершине $$x$$, не окрашено в этот цвет. Веером называется подграф $$F(x,y_{1}\ldots y_{k}$$, $$\alpha _{1}\ldots \alpha _{k})$$, состоящий из вершин $$x,y_{1} \ldots y_{k}$$ и ребер $$(x,y_{1})\ldots (x,y_{k} )$$, в котором:

  • ребро $$(x,y_{1})$$ не окрашено;
  • ребро $$(x,y_{i})$$ окрашено в цвет $$\alpha_{i-1}$$, $$i=2\ldots k$$ ;
  • в вершине $$y_{i}$$ отсутствует цвет $$\alpha_{i}$$, $$i=1\ldots k$$ ;
  • $$\alpha_{1}\ldots \alpha_{k-1}$$ все попарно различны.
    •

    Перекраска веера состоит в том, что ребра $$(x,y_{1})\ldots (x,y_{k-1})$$ окрашиваются соответственно в цвета $$\alpha_{1}\ldots \alpha_{k-1}$$, а ребро $$(x,y_{k})$$ становится неокрашенным. Очевидно, новая частичная раскраска тоже будет правильной. На рис. 10.3 слева показан веер, а справа - результат его перекраски. Цвета ребер представлены числами, а отсутствующие цвета в вершинах - числами со знаком минус. Неокрашенное ребро изображено пунктиром.

    (рис 10.3)

    Покажем, что с помощью этих двух процедур перекрашивания можно ребра любого графа $$G$$ окрасить в не более чем $$\Delta (G)+1$$ цветов. Допустим, что уже построена частичная правильная раскраска, использующая не более чем $$\Delta (G)+1$$ цветов, и имеется неокрашенное ребро $$(x,y)$$. Так как число разрешенных цветов больше, чем максимальная степень вершины, то в каждой вершине какой-нибудь цвет отсутствует. Допустим, в вершине $$x$$ отсутствует цвет $$\beta$$.

    Будем строить веер следующим образом. Положим $$y_{1} =y$$ и пусть $$\alpha_{1}$$ - цвет, отсутствующий в вершине $$y$$. Получаем веер $$F(x,y_{1},\alpha_{1})$$. Допустим, веер $$F(x,y_{1} \ldots y_{k}, \alpha_{1}\ldots \alpha_{k})$$ уже построен. Если цвет $$\alpha_{k}$$ отличен от $$\alpha_{1}\ldots \alpha_{k-1}$$ и имеется инцидентное вершине $$x$$ ребро $$(x,z)$$ этого цвета, то увеличиваем $$k$$ на 1 и полагаем $$y_{k} =z$$, $$\alpha_{k}$$ - цвет, отсутствующий в вершине $$z$$. Этот процесс построения веера продолжается до тех пор, пока не наступит одно из следующих событий.

    (А) Нет ребра цвета $$\alpha_{k}$$, инцидентного вершине $$x$$. Перекрашиваем веер, в результате ребро $$(x,y)$$ становится окрашенным, а ребро $$(x,y_{k})$$ - неокрашенным, причем цвет $$\alpha_{k}$$ отсутствует и в вершине $$y_{k}$$, и в вершине $$x$$. Но тогда можно это ребро окрасить в цвет $$\alpha_{k}$$, и мы получим правильную раскраску, в которой на одно окрашенное ребро больше.

    (Б) Цвет $$\alpha_{k}$$ совпадает с одним из цветов $$\alpha_{1}\ldots \alpha_{k-1}$$ (именно этот случай изображен на рис. 10.3). Пусть $$\alpha_{k} =\alpha_{i}$$. Рассмотрим вершины $$x,y_{i},y_{k}$$. В каждой из них отсутствует какой-нибудь из цветов $$\beta$$ или $$\alpha_{k}$$. Значит, в подграфе, образованном ребрами этих двух цветов, степень каждой из этих вершин не превосходит 1. Следовательно, все три вершины не могут принадлежать одной $$(\alpha_{k},\beta)$$ -компоненте. Рассмотрим две возможности.

    (Б1) Вершины $$x$$ и $$y_{i}$$ принадлежат разным $$(\alpha_{k},\beta )$$ -компонентам. Перекрасим веер $$F(x,y_{1}\ldots y_{i},\alpha _{1}\ldots \alpha _{i})$$. Ребро $$(x,y_{i} )$$ станет неокрашенным. Теперь перекрасим $$(\alpha_{k},\beta )$$ -компоненту, содержащую вершину $$y_{i}$$. После этого цвет $$\beta$$ будет отсутствовать в вершине $$y_{i}$$ и ребро $$(x,y_{i})$$ можно окрасить в этот цвет.

    (Б2) Вершины $$x$$ и $$y_{k}$$ принадлежат разным $$(\alpha_{k},\beta)$$ -компонентам. Перекрасим веер $$F(x,y_{1}\ldots y_{k},\alpha _{1} \ldots \alpha _{k})$$. Ребро $$(x,y_{k})$$ станет неокрашенным. Теперь перекрасим $$(\alpha_{k},\beta)$$ -компоненту, содержащую вершину $$y_{k}$$. После этого цвет $$\beta$$ будет отсутствовать в вершине $$y_{k}$$ и ребро $$(x,y_{k})$$ можно окрасить в этот цвет.

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

    На рис. 10.4 иллюстрируются случаи (Б1) и (Б2) на примере веера из рисунка 10.3. Здесь $$k=5$$, $$i=3$$. Левое изображение соответствует случаю (Б1): вершины $$x$$ и $$y_{3}$$ принадлежат разным $$(3, 5)$$ -компонентам. После перекраски веера $$F(x,y_{1} ,y_{2} ,y_{3} ,1,2,3)$$ и $$(3,5)$$ -компоненты, содержащей вершину $$y_{3}$$, появляется возможность окрасить ребро $$(x,y_{3})$$ в цвет 5. Случай (Б2) показан справа: здесь вершины $$x$$ и $$y_{5}$$ принадлежат разным $$(3, 5)$$ -компонентам, поэтому после перекраски веера $$F(x,y_{1},y_{2},y_{3}, y_{4}, y_{5}$$, $$1$$, $$2$$, $$3$$, $$4,3)$$ и $$(3,5)$$ -компоненты, содержащей вершину $$y_{5}$$, появляется возможность окрасить ребро $$(x,y_{5})$$ в цвет 5.

    (рис 10.4)

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

    Страницы:

    Раскраска вершин

    Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа $$1, 2\ldots k$$. Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве $$\{ 1,2\ldots k\}$$. Раскраску можно также рассматривать как разбиение множества вершин $$V=V_{1} \cup V_{2} \cup \ldots \cup V_{k}$$, где $$V_{i}$$ - множество вершин цвета $$i$$. Множества $$V_{i}$$ называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа $$G$$ в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается $$\chi(G)$$.

    В правильной раскраске полного графа $$K_{n}$$ все вершины должны иметь разные цвета, поэтому $$\chi (K_{n} )=n$$. Если в каком-нибудь графе имеется полный подграф с $$k$$ вершинами, то для раскраски этого подграфа необходимо $$k$$ цветов. Отсюда следует, что для любого графа выполняется неравенство

    $$\chi(G)\ge \omega (G).$$

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

    (рис 10.1)

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

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

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

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

    Выберем в данном графе $$G$$ две несмежные вершины $$x$$ и $$y$$ и построим два новых графа: $$G_{1}$$, получающийся добавлением ребра $$(x,y)$$ к графу $$G$$, и $$G_{2}$$, получающийся из $$G$$ слиянием вершин $$x$$ и $$y$$. Операция слияния состоит в удалении вершин $$x$$ и $$y$$ и добавлении новой вершины $$z$$ и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин $$x$$, $$y$$. На рис. 10.2 показаны графы $$G_{1}$$ и $$G_{2}$$, получающиеся из графа $$G$$, изображенного на рис. 10.1, с помощью этих операций, если в качестве $$x$$ и $$y$$ взять вершины $$a$$ и $$f$$.

    (рис 10.2)

    Если в правильной раскраске графа $$G$$ вершины $$x$$ и $$y$$ имеют разные цвета, то она будет правильной и для графа $$G_{1}$$. Если же цвета вершин $$x$$ и $$y$$ в раскраске графа $$G$$ одинаковы, то граф $$G_{2}$$ можно раскрасить в то же число цветов: новая вершина $$z$$ окрашивается в тот цвет, в который окрашены вершины $$x$$ и $$y$$, а все остальные вершины сохраняют те цвета, которые они имели в графе $$G$$. И наоборот, раскраска каждого из графов $$G_{1}$$, $$G_{2}$$, очевидно, дает раскраску графа $$G$$ в то же число цветов. Поэтому

    $$\chi (G)=\min \{ \chi (G_{1}),\chi (G_{2})\},$$

    что дает возможность рекурсивного нахождения раскраски графа в минимальное число цветов. Заметим, что граф $$G_{1}$$ имеет столько же вершин, сколько исходный граф, но у него больше ребер. Поэтому рекурсия в конечном счете приводит к полным графам, для которых задача о раскраске решается тривиально.

    Раскраска ребер

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

    Обозначим через $$\Delta (G)$$ максимальную степень вершины в графе. При правильной реберной раскраске все ребра, инцидентные одной вершине, должны иметь разные цвета. Отсюда следует, что для любого графа выполняется неравенство $$\chi'(G)\ge \Delta (G)$$. Для некоторых графов имеет место строгое неравенство, например, $$\Delta (C_{3} )=2$$, а $$\chi'(C_{3} )=3$$. Следующая теорема, доказанная В.Г.Визингом в 1964 г., показывает, что $$\chi'(G)$$ может отличаться от $$\Delta(G)$$ не более чем на 1.

    Теорема 1. Для любого графа $$G$$ справедливы неравенства $${\Delta (G)\le \chi'(G)\le \Delta (G)+1}$$.

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

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

    Другая операция применяется к частично раскрашенному подграфу, называемому веером. Будем говорить, что при данной раскраске цвет $$\alpha$$ отсутствует в вершине $$x$$, если ни одно из ребер, инцидентных вершине $$x$$, не окрашено в этот цвет. Веером называется подграф $$F(x,y_{1}\ldots y_{k}$$, $$\alpha _{1}\ldots \alpha _{k})$$, состоящий из вершин $$x,y_{1} \ldots y_{k}$$ и ребер $$(x,y_{1})\ldots (x,y_{k} )$$, в котором:

  • ребро $$(x,y_{1})$$ не окрашено;
  • ребро $$(x,y_{i})$$ окрашено в цвет $$\alpha_{i-1}$$, $$i=2\ldots k$$ ;
  • в вершине $$y_{i}$$ отсутствует цвет $$\alpha_{i}$$, $$i=1\ldots k$$ ;
  • $$\alpha_{1}\ldots \alpha_{k-1}$$ все попарно различны.
    •

    Перекраска веера состоит в том, что ребра $$(x,y_{1})\ldots (x,y_{k-1})$$ окрашиваются соответственно в цвета $$\alpha_{1}\ldots \alpha_{k-1}$$, а ребро $$(x,y_{k})$$ становится неокрашенным. Очевидно, новая частичная раскраска тоже будет правильной. На рис. 10.3 слева показан веер, а справа - результат его перекраски. Цвета ребер представлены числами, а отсутствующие цвета в вершинах - числами со знаком минус. Неокрашенное ребро изображено пунктиром.

    (рис 10.3)

    Покажем, что с помощью этих двух процедур перекрашивания можно ребра любого графа $$G$$ окрасить в не более чем $$\Delta (G)+1$$ цветов. Допустим, что уже построена частичная правильная раскраска, использующая не более чем $$\Delta (G)+1$$ цветов, и имеется неокрашенное ребро $$(x,y)$$. Так как число разрешенных цветов больше, чем максимальная степень вершины, то в каждой вершине какой-нибудь цвет отсутствует. Допустим, в вершине $$x$$ отсутствует цвет $$\beta$$.

    Будем строить веер следующим образом. Положим $$y_{1} =y$$ и пусть $$\alpha_{1}$$ - цвет, отсутствующий в вершине $$y$$. Получаем веер $$F(x,y_{1},\alpha_{1})$$. Допустим, веер $$F(x,y_{1} \ldots y_{k}, \alpha_{1}\ldots \alpha_{k})$$ уже построен. Если цвет $$\alpha_{k}$$ отличен от $$\alpha_{1}\ldots \alpha_{k-1}$$ и имеется инцидентное вершине $$x$$ ребро $$(x,z)$$ этого цвета, то увеличиваем $$k$$ на 1 и полагаем $$y_{k} =z$$, $$\alpha_{k}$$ - цвет, отсутствующий в вершине $$z$$. Этот процесс построения веера продолжается до тех пор, пока не наступит одно из следующих событий.

    (А) Нет ребра цвета $$\alpha_{k}$$, инцидентного вершине $$x$$. Перекрашиваем веер, в результате ребро $$(x,y)$$ становится окрашенным, а ребро $$(x,y_{k})$$ - неокрашенным, причем цвет $$\alpha_{k}$$ отсутствует и в вершине $$y_{k}$$, и в вершине $$x$$. Но тогда можно это ребро окрасить в цвет $$\alpha_{k}$$, и мы получим правильную раскраску, в которой на одно окрашенное ребро больше.

    (Б) Цвет $$\alpha_{k}$$ совпадает с одним из цветов $$\alpha_{1}\ldots \alpha_{k-1}$$ (именно этот случай изображен на рис. 10.3). Пусть $$\alpha_{k} =\alpha_{i}$$. Рассмотрим вершины $$x,y_{i},y_{k}$$. В каждой из них отсутствует какой-нибудь из цветов $$\beta$$ или $$\alpha_{k}$$. Значит, в подграфе, образованном ребрами этих двух цветов, степень каждой из этих вершин не превосходит 1. Следовательно, все три вершины не могут принадлежать одной $$(\alpha_{k},\beta)$$ -компоненте. Рассмотрим две возможности.

    (Б1) Вершины $$x$$ и $$y_{i}$$ принадлежат разным $$(\alpha_{k},\beta )$$ -компонентам. Перекрасим веер $$F(x,y_{1}\ldots y_{i},\alpha _{1}\ldots \alpha _{i})$$. Ребро $$(x,y_{i} )$$ станет неокрашенным. Теперь перекрасим $$(\alpha_{k},\beta )$$ -компоненту, содержащую вершину $$y_{i}$$. После этого цвет $$\beta$$ будет отсутствовать в вершине $$y_{i}$$ и ребро $$(x,y_{i})$$ можно окрасить в этот цвет.

    (Б2) Вершины $$x$$ и $$y_{k}$$ принадлежат разным $$(\alpha_{k},\beta)$$ -компонентам. Перекрасим веер $$F(x,y_{1}\ldots y_{k},\alpha _{1} \ldots \alpha _{k})$$. Ребро $$(x,y_{k})$$ станет неокрашенным. Теперь перекрасим $$(\alpha_{k},\beta)$$ -компоненту, содержащую вершину $$y_{k}$$. После этого цвет $$\beta$$ будет отсутствовать в вершине $$y_{k}$$ и ребро $$(x,y_{k})$$ можно окрасить в этот цвет.

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

    На рис. 10.4 иллюстрируются случаи (Б1) и (Б2) на примере веера из рисунка 10.3. Здесь $$k=5$$, $$i=3$$. Левое изображение соответствует случаю (Б1): вершины $$x$$ и $$y_{3}$$ принадлежат разным $$(3, 5)$$ -компонентам. После перекраски веера $$F(x,y_{1} ,y_{2} ,y_{3} ,1,2,3)$$ и $$(3,5)$$ -компоненты, содержащей вершину $$y_{3}$$, появляется возможность окрасить ребро $$(x,y_{3})$$ в цвет 5. Случай (Б2) показан справа: здесь вершины $$x$$ и $$y_{5}$$ принадлежат разным $$(3, 5)$$ -компонентам, поэтому после перекраски веера $$F(x,y_{1},y_{2},y_{3}, y_{4}, y_{5}$$, $$1$$, $$2$$, $$3$$, $$4,3)$$ и $$(3,5)$$ -компоненты, содержащей вершину $$y_{5}$$, появляется возможность окрасить ребро $$(x,y_{5})$$ в цвет 5.

    (рис 10.4)

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

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^