Алгоритм раскраски рёбер Мисры и Гриса

Алгоритм раскраски рёбер Мисры и Гриса — это алгоритм полиномиального времени в теории графов, который находит рёберную раскраску любого графа. Раскраска требует максимум $\Delta +1$ цветов, где $\Delta$ — максимальная степень графа. Это значение оптимально для некоторых графов, а по теореме Визинга оно на один цвет больше, чем оптимальная раскраска остальных графов.

Алгоритм опубликовали в 1992 году Джаядев Мисра и Дэвид Грис. Он является упрощением алгоритма Белы Болобаша.

Этот алгоритм является самым быстрым из известных почти оптимальных алгоритмов раскраски рёбер, выполняющимся за время $O(|E||V|)$. Более быстрый алгоритм со временем $O(|E|{\sqrt {|V|\log |V|}})$ объявлен в 1985 в техническом отчёте Габова и др., но так и не опубликован.

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

Веера

Веер F=[x_1,x_2,x_3] вершины v (пунктирное ребро не выкрашено), (v, x_1), (v, x_2), (v, x_3) являются рёбрами веера. F'=[x_1,x_2] также является веером вершины v, но он не максимален.

Говорят, что цвет x отсутствует в вершине u, если $c(u,z)\neq x$ для всех (u, z) $\in$ E(G).

Веер в вершине u — это последовательность вершин F[1:k], которая удовлетворяет следующим условиям:

1. F[1:k] является непустой последовательностью различных соседей вершины u
2. Ребро (F[1], u) $\in$ E(G) не выкрашено
3. Цвет ребра (F[i+1], u) отсутствует в вершине F[i] для $1\leqslant i<k$

Примеры cd_x путей: ac, cg, gd является красно-зелёным_c путём, а bd, dg является оранжево-красным_d путём.

Если дан веер F, любое ребро (F[i], X) для $1\leqslant i\leqslant k$ является ребром веера. Пусть c и d будут двумя цветами. Путь cd_X — это путь, который проходит через вершину X, содержит только рёбра с цветами c и d и является максимальным (мы не можем добавить какое-либо ребро цветом из {c, d}). Заметим, что существует для X только один такой путь, так как максимум одно ребро каждого цвета может быть смежно заданной вершине.

Вращение веера

Вращение левого веера $F=[x_{1},x_{2},x_{3}]$ приводит к вееру справа

Если дан веер F[1:k] вершины X, операция «вращения веера» делает следующее (одновременно):

1. $c(F[i],X)=c(F[i+1],X)$
2. Снимает раскраску ребра (F[k],X)

Эта операция оставляет раскраску правильной, поскольку для каждого i цвет $c(F[i+1],X)$ отсутствовал в $(F[i],X)$.

Обращение пути

Обращение красно-зелёного_a пути в левом графе приводит к правому графу.

Операция «перекраска пути cd_X» меняет все цвета c на пути на d и все цвета d на c. Обращение пути может быть полезным для освобождения цвета в X, если X является конечной вершиной пути — если вершина X была смежна цвету c, но не d, теперь она будет смежна цвету d, но не c, что освобождает цвет c для другого ребра, смежного X. Применение операции не нарушает допустимость раскраски, поскольку для конечных вершин только один из цветов из {c, d} может быть смежен вершине, а для других элементов пути операция лишь переключает цвета рёбер, никакого нового цвета не добавляется.

Алгоритм

Вход: Граф G.

Выход: Правильная раскраска рёбер графа G

Положим U := E(G)

Пока U ≠ ∅ выполнить

1. Возьмём любое ребро (u, v) из U.
2. Пусть F[1:k] будет максимальным веером u, начинающимся в F[1]=v.
3. Пусть c будет цветом, который отсутствует в u и d будет цветом, отсутствующим в F[k].
4. Обращаем путь cd_u
5. Пусть $w\in V(G)$ будет таким, что $w\in F,F'=[F[1]\dots w]$ является веером, а d отсутствует в w.
6. Вращаем F' и положим c(u, w)=d.
7. U := U — {(u, v)}

конец Пока

Доказательство корректности

Корректность алгоритма доказывается в три этапа. Сначала показывается, что перекраска пути cd_u гарантирует вершину w, такую что $w\in F,F'=[F[1]\dots w]$ является веером и d отсутствует в w. Тогда эта раскраска рёбер будет правильной и требует не более $\Delta +1$ цветов.

Инверсия пути

До перекраски пути возможны два случая:

1. Веер не имеет рёбер, выкрашенных в d. Поскольку F является максимальным веером и d отсутствует в F[k], из этого следует, что не существует ребра с цветом d, смежного u. В противном случае, если бы такое ребро существовало, его можно было бы присоединить к F[k], так как d отсутствует в F[k], но F максимален, получаем противоречие. Тогда d отсутствует в u и, поскольку c также отсутствует в u, путь cd_u пуст и инверсия не влияет на граф. Положим $w=F[k]$.
2. Веер имеет одно ребро с цветом d. Пусть (u,F[x+1]) будет этим ребром. Заметим, что $x+1\neq 1$, поскольку (u,F[1]) не выкрашено. Тогда цвет d отсутствует в F[x]. Также $x\neq k$, поскольку веер имеет длину k, но существует $F[x+1]$. Мы можем теперь показать, что после перекраски для каждого $y\in \{1,\dots ,x-1,x+1,\dots ,k\}$ цвет $(F[y+1],u)$ отсутствует в F[y]. Заметим, что до перекраски цвет $(u,F[y+1])$ не совпадал ни с c, ни с d, поскольку c отсутствует в u, а $(u,F[x+1])$ содержит цвет d и раскраска правильна. Обращение влияет только на рёбра, которые выкрашены в c или d, так что (1) выполняется.

F[x] может содержаться в пути cd_u или нет. Если оно не содержится в пути, то перекраска не влияет на множество отсутствующих цветов в F[x] и d останется отсутствующим в нём. Мы можем положить $w=F[x]$. В противном случае мы можем показать, что F остаётся веером и d остаётся отсутствующим в F[k]. Поскольку d отсутствовал в F[x] до перекраски, а F[x] находится на пути, F[x] является конечной вершиной пути cd_u и c будет отсутствовать в F[x] после перекраски. Перекраска изменит цвет $(u,F[x+1])$ с d на c. Тогда, поскольку c теперь отсутствует в F[x] и выполняется (1), F остаётся веером. Также d остаётся отсутствующим в F[k], поскольку F[k] не на пути cd_u (предположим, что оно на пути, но, поскольку d отсутствует в F[k], он должен быть конечной точкой пути, однако конечными точками являются u и F[x]). Выберем $w=F[k]$.

В любом случае, веер $F'$ является префиксом F, откуда следует что $F'$ также является веером.

Раскраска рёбер правильна

Это можно показать методом математической индукции по числу раскрашенных рёбер. База индукции: нет раскрашенных рёбер, раскраска правильная. Шаг индукции: предположим, что раскраска была правильной на предыдущей итерации. На текущей итерации после перекраски пути d становится отсутствующим в u и по предыдущему результату он будет отсутствовать в w. Вращение $F'$ не разрушает правильности раскраски. Тогда, после того как положим $c(u,w)=d$, раскраска остаётся правильной.

Алгоритм требует максимум $\Delta +1$ цветов

На заданном шаге используются только цвета c и d. Поскольку u смежна по меньшей мере с одним нераскрашенным ребром и её степень ограничена $\Delta$, по меньшей мере один цвет из $\{1,\dots ,\Delta \}$ доступен для c. Для d F[k] может иметь степень $\Delta$ и не иметь нераскрашенных смежных рёбер. Тогда может потребоваться $\Delta +1$ цветов.

Сложность

На каждом шаге вращение снимает раскраску ребра (u, w), раскрашивая при этом рёбра (u,F[1]) и (u, v), которые до этого цвета не имели. Таким образом, появляется одно дополнительное раскрашенное ребро. Следовательно, цикл будет выполнен $O(|E|)$ раз. Поиск максимального веера, цветов c и d и перекраска пути cd_u могут быть выполнены за время $O(|V|)$. Нахождение w и вращение F' занимает $O(\deg(u))\in O(|V|)$ времени. Поиск и удаление ребра (u, v) могут быть осуществлены с помощью стека за постоянное время (операция выборки последнего элемента) и этот стек может быть заполнен за время $O(|E|)$. Таким образом, каждая операция цикла занимает $O(|V|)$ времени и общее время работы алгоритма равно $O(|E|+|E||V|)=O(|E||V|)$.

Литература

• Jayadev Misra, David Gries. A constructive proof of Vizing's theorem // Information Processing Letters. — 1992. — Т. 41, вып. 3. — doi:10.1016/0020-0190(92)90041-S.
• Béla Bollobás. Graph theory. — Elsevier, 1982.
• Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algorithms for edge-coloring graphs. — Tohoku University, 1985. — (Tech. Report TRECIS-8501).