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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Этот алгоритм является самым быстрым из известных почти оптимальных алгоритмов раскраски рёбер, выполняющимся за время . Более быстрый алгоритм со временем объявлен в 1985 в техническом отчёте Габова и др., но так и не опубликован[3].

Как правило, оптимальная раскраска рёбер является 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, если для всех (u, z) E(G).

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

  1. F[1:k] является непустой последовательностью различных соседей вершины u
  2. Ребро (F[1], u) E(G) не выкрашено
  3. Цвет ребра (F[i+1], u) отсутствует в вершине F[i] для
Примеры cdx путей: ac, cg, gd является красно-зелёнымc путём, а bd, dg является оранжево-краснымd путём.

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

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

[править | править код]
Вращение левого веера приводит к вееру справа

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

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

Эта операция оставляет раскраску правильной, поскольку для каждого i цвет отсутствовал в .

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

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

Операция «перекраска пути cdX» меняет все цвета 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. Обращаем путь cdu
  5. Пусть будет таким, что является веером, а d отсутствует в w.
  6. Вращаем F' и положим c(u, w)=d.
  7. U := U — {(u, v)}

конец Пока

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

[править | править код]

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

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

[править | править код]

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

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

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

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

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

[править | править код]

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

Алгоритм требует максимум цветов

[править | править код]

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

На каждом шаге вращение снимает раскраску ребра (u, w), раскрашивая при этом рёбра (u,F[1]) и (u, v), которые до этого цвета не имели. Таким образом, появляется одно дополнительное раскрашенное ребро. Следовательно, цикл будет выполнен раз. Поиск максимального веера, цветов c и d и перекраска пути cdu могут быть выполнены за время . Нахождение w и вращение F' занимает времени. Поиск и удаление ребра (u, 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).