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

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

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

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

Веера

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

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

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

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

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

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

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

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

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

Операция «перекраска пути 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. Пусть ${\displaystyle w\in V(G)}$ будет таким, что ${\displaystyle w\in F,F'=[F[1]\dots w]}$ является веером, а d отсутствует в w.
6. Вращаем F' и положим c(u, w)=d.
7. U := U — {(u, v)}

конец Пока

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

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

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

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

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

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

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

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

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

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

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

Сложность

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

Примечания

Литература

• Jayadev Misra, David Gries . // . — 1992. — Т. 41 , вып. 3 . — doi : .
• 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).