Русская Википедия:Алгоритм раскраски рёбер Мисры и Гриса
Алгоритм раскраски рёбер Мисры и Гриса — это алгоритм полиномиального времени в теории графов, который находит рёберную раскраску любого графа. Раскраска требует максимум <math>\Delta+1</math> цветов, где <math>\Delta</math> — максимальная степень графа. Это значение оптимально для некоторых графов, а по теореме Визинга оно на один цвет больше, чем оптимальная раскраска остальных графов.
Алгоритм опубликовали в 1992 году Джаядев Мисра и Дэвид ГрисШаблон:Sfn. Он является упрощением алгоритма Белы БолобашаШаблон:Sfn.
Этот алгоритм является самым быстрым из известных почти оптимальных алгоритмов раскраски рёбер, выполняющимся за время <math>O(|E||V|)</math>. Более быстрый алгоритм со временем <math>O(|E|\sqrt{|V|\log|V|})</math> объявлен в 1985 в техническом отчёте Габова и др., но так и не опубликованШаблон:Sfn.
Как правило, оптимальная раскраска рёбер является NP-полной задачей, так что вряд ли для этой задачи алгоритм полиномиального времени существует. Существуют, однако, алгоритмы точной раскраски рёбер с экспоненциальным временем работы, которые дают оптимальное решение.
Веера
Говорят, что цвет x отсутствует в вершине u, если <math>c(u,z) \ne x</math> для всех (u, z) <math>\in</math> E(G).
Веер в вершине u — это последовательность вершин F[1:k], которая удовлетворяет следующим условиям:
- F[1:k] является непустой последовательностью различных соседей вершины u
- Ребро (F[1], u) <math>\in</math> E(G) не выкрашено
- Цвет ребра (F[i+1], u) отсутствует в вершине F[i] для <math>1 \leqslant i < k</math>
Если дан веер F, любое ребро (F[i], X) для <math>1 \leqslant i \leqslant k</math> является ребром веера. Пусть c и d будут двумя цветами. Путь cdX — это путь, который проходит через вершину X, содержит только рёбра с цветами c и d и является максимальным (мы не можем добавить какое-либо ребро цветом из {c, d}). Заметим, что существует для X только один такой путь, так как максимум одно ребро каждого цвета может быть смежно заданной вершине.
Вращение веера
Если дан веер F[1:k] вершины X, операция «вращения веера» делает следующее (одновременно):
- c(F[i],X)=c(F[i+1],X)
- Снимает раскраску ребра (F[k],X)
Эта операция оставляет раскраску правильной, поскольку для каждого i цвет <math>c(F[i + 1], X)</math> отсутствовал в <math>(F[i],X)</math>.
Обращение пути
Операция «перекраска пути cdX» меняет все цвета c на пути на d и все цвета d на c. Обращение пути может быть полезным для освобождения цвета в X, если X является конечной вершиной пути — если вершина X была смежна цвету c, но не d, теперь она будет смежна цвету d, но не c, что освобождает цвет c для другого ребра, смежного X. Применение операции не нарушает допустимость раскраски, поскольку для конечных вершин только один из цветов из {c, d} может быть смежен вершине, а для других элементов пути операция лишь переключает цвета рёбер, никакого нового цвета не добавляется.
Алгоритм
Вход: Граф G.
Выход: Правильная раскраска рёбер графа G
Положим U := E(G)
Пока U ≠ ∅ выполнить
- Возьмём любое ребро (u, v) из U.
- Пусть F[1:k] будет максимальным веером u, начинающимся в F[1]=v.
- Пусть c будет цветом, который отсутствует в u и d будет цветом, отсутствующим в F[k].
- Обращаем путь cdu
- Пусть <math>w \in V(G)</math> будет таким, что <math>w \in F, F'=[F[1]\dots w]</math> является веером, а d отсутствует в w.
- Вращаем F' и положим c(u, w)=d.
- U := U — {(u, v)}
конец Пока
Доказательство корректности
Корректность алгоритма доказывается в три этапа. Сначала показывается, что перекраска пути cdu гарантирует вершину w, такую что <math>w \in F, F'=[F[1]\dots w]</math> является веером и d отсутствует в w. Тогда эта раскраска рёбер будет правильной и требует не более <math>\Delta + 1</math> цветов.
Инверсия пути
До перекраски пути возможны два случая:
- Веер не имеет рёбер, выкрашенных в d. Поскольку F является максимальным веером и d отсутствует в F[k], из этого следует, что не существует ребра с цветом d, смежного u. В противном случае, если бы такое ребро существовало, его можно было бы присоединить к F[k], так как d отсутствует в F[k], но F максимален, получаем противоречие. Тогда d отсутствует в u и, поскольку c также отсутствует в u, путь cdu пуст и инверсия не влияет на граф. Положим <math>w=F[k]</math>.
- Веер имеет одно ребро с цветом d. Пусть (u,F[x+1]) будет этим ребром. Заметим, что <math>x + 1 \ne 1</math>, поскольку (u,F[1]) не выкрашено. Тогда цвет d отсутствует в F[x]. Также <math>x \ne k</math>, поскольку веер имеет длину k, но существует <math>F[x + 1]</math>. Мы можем теперь показать, что после перекраски для каждого <math>y \in \{1, \dots, x - 1, x + 1, \dots, k\}</math> цвет <math>(F[y + 1], u)</math> отсутствует в F[y]. Заметим, что до перекраски цвет <math>(u, F[y + 1])</math> не совпадал ни с c, ни с d, поскольку c отсутствует в u, а <math>(u, F[x + 1])</math> содержит цвет d и раскраска правильна. Обращение влияет только на рёбра, которые выкрашены в c или d, так что (1) выполняется.
F[x] может содержаться в пути cdu или нет. Если оно не содержится в пути, то перекраска не влияет на множество отсутствующих цветов в F[x] и d останется отсутствующим в нём. Мы можем положить <math>w=F[x]</math>. В противном случае мы можем показать, что F остаётся веером и d остаётся отсутствующим в F[k]. Поскольку d отсутствовал в F[x] до перекраски, а F[x] находится на пути, F[x] является конечной вершиной пути cdu и c будет отсутствовать в F[x] после перекраски. Перекраска изменит цвет <math>(u, F[x + 1])</math> с d на c. Тогда, поскольку c теперь отсутствует в F[x] и выполняется (1), F остаётся веером. Также d остаётся отсутствующим в F[k], поскольку F[k] не на пути cdu (предположим, что оно на пути, но, поскольку d отсутствует в F[k], он должен быть конечной точкой пути, однако конечными точками являются u и F[x]). Выберем <math>w=F[k]</math>.
В любом случае, веер <math>F'</math> является префиксом F, откуда следует что <math>F'</math> также является веером.
Раскраска рёбер правильна
Это можно показать методом математической индукции по числу раскрашенных рёбер. База индукции: нет раскрашенных рёбер, раскраска правильная. Шаг индукции: предположим, что раскраска была правильной на предыдущей итерации. На текущей итерации после перекраски пути d становится отсутствующим в u и по предыдущему результату он будет отсутствовать в w. Вращение <math>F'</math> не разрушает правильности раскраски. Тогда, после того как положим <math>c(u,w)=d</math>, раскраска остаётся правильной.
Алгоритм требует максимум <math>\Delta + 1</math> цветов
На заданном шаге используются только цвета c и d. Поскольку u смежна по меньшей мере с одним нераскрашенным ребром и её степень ограничена <math>\Delta</math>, по меньшей мере один цвет из <math>\{1,\dots,\Delta\}</math> доступен для c. Для d F[k] может иметь степень <math>\Delta</math> и не иметь нераскрашенных смежных рёбер. Тогда может потребоваться <math>\Delta + 1</math> цветов.
Сложность
На каждом шаге вращение снимает раскраску ребра (u, w), раскрашивая при этом рёбра (u,F[1]) и (u, v), которые до этого цвета не имели. Таким образом, появляется одно дополнительное раскрашенное ребро. Следовательно, цикл будет выполнен <math>O(|E|)</math> раз. Поиск максимального веера, цветов c и d и перекраска пути cdu могут быть выполнены за время <math>O(|V|)</math>. Нахождение w и вращение F' занимает <math>O(\deg(u))\in O(|V|)</math> времени. Поиск и удаление ребра (u, v) могут быть осуществлены с помощью стека за постоянное время (операция выборки последнего элемента) и этот стек может быть заполнен за время <math>O(|E|)</math>. Таким образом, каждая операция цикла занимает <math>O(|V|)</math> времени и общее время работы алгоритма равно <math>O(|E|+|E||V|)=O(|E||V|)</math>.
Примечания
Литература
