Алгоритм раскраски краев Misra & Gries - Misra & Gries edge coloring algorithm

В Алгоритм окраски краев Misra & Gries это полиномиальное время алгоритм в теория графов что находит окраска края любого графа. Окраска позволяет использовать не более ${ displaystyle Delta +1}$ цвета, где ${ displaystyle Delta}$ это максимум степень графа. Это оптимально для некоторых графиков, и по Теорема Визинга он использует максимум на один цвет больше, чем оптимальный для всех остальных.

Впервые он был опубликован Джаядев Мишра и Дэвид Грис в 1992 г.^[1] Это упрощение предыдущего алгоритма за счет Béla Bollobás.^[2]

Этот алгоритм является самым быстрым из известных почти оптимальных алгоритмов окраски ребер, выполняемых в ${ Displaystyle O (| E || V |)}$ время. Более быстрый временной интервал ${ Displaystyle O (| E | { sqrt {| V | log | V |}})}$ было заявлено в техническом отчете 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, но не максимальный.

Цвет Икс как говорят свободный края (u, v) на ты если с (и, z) ≠ Икс для всех (u, z) ${ displaystyle in}$ E (G): z ≠ v.

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

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

Примеры компакт-дисков_Икс пути: ac, cg, gd - красно-зеленый_{_c} path и bd, dg - красно-оранжевый_d дорожка.

Для веера F любое ребро (F [i], X) для 1 ≤ i ≤ k является край вентилятора. Пусть c и d - цвета. Компакт-диск_Икс-path - это реберный путь, который проходит через вершину X, содержит только ребра, окрашенные c и d, и является максимальным (мы не можем добавить никакое другое ребро, так как оно будет включать ребра с цветом не в {c, d}). Обратите внимание, что для вершины X существует только один такой путь, так как не более одного ребра каждого цвета может быть смежным с данной вершиной.

Вращающийся вентилятор

Вращение вентилятора F = [Икс₁, Икс₂, Икс₃] слева дает веер справа

Учитывая вентилятор F[1:k] вершины Икс, операция "вращение вентилятора" выполняет (параллельно) следующее:

c (F [i], X) = c (F [i + 1], X)
Бесцветный (F [k], X)

Эта операция оставляет в силе раскраску, так как для каждого я, c(F[я + 1], Икс) был свободен на (F[я], Икс).

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

Инвертирование красно-зеленого_а путь от графика слева приводит к графику справа.

Операция "инвертировать компакт-диск_Икс-path "переключает каждое ребро на пути, окрашенном с c в d, и каждое ребро, окрашенное с d на c. Инвертирование пути может быть полезно для освобождения цвета на X, если X является одной из конечных точек пути: если X был смежным с цветом c, но не d, теперь он будет рядом с цветом d, а не c, освобождая c для другого ребра, смежного с X. Операция переворота не изменит действительность раскраски, поскольку для конечных точек только одна из {c, d} может быть смежным с вершиной, а для других элементов пути операция меняет только цвет ребер, новый цвет не добавляется.

Алгоритм

алгоритм Алгоритм окраски краев Misra & Gries является    Вход: Граф Г. выход: Правильная раскраска c ребер графа G. Пусть U: = E (G) пока U ≠ ∅ делать        Пусть (u, v) - любое ребро в U. Пусть F [1: k] - максимальный веер u, начинающийся в F [1] = v. Пусть c - цвет, свободный на u, а d - цвет, который свободен на F [k]. Переверните компакт-диск_ты path Пусть w ∈ V (G) таков, что w ∈ F, F '= [F [1] ... w] веер и d свободно на w. Поверните F 'и установите c (u, w) = d. U: = U - {(u, v)} конец пока

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

Правильность алгоритма доказывается в трех частях. Во-первых, показано, что инверсия cd_ты path гарантирует такую вершину w, что ш ∈ F, F' = [F[1]...ш] фанат и d бесплатно наш. Затем показано, что раскраска ребер правильная и требует не более Δ + 1 цвета.

Гарантия инверсии пути

До инверсии есть два случая:

Вентилятор не имеет окрашенного края d. С F является максимальным веером и d бесплатно на F[k], это означает, что края с цветом d рядом с ты, иначе, если бы был, это ребро было бы после F[k], в качестве d бесплатно на F[k], но F был максимальным, противоречие. Таким образом, d бесплатно на ты, и с тех пор c также бесплатно на ты, то CD_ты путь пуст, и инверсия не влияет на график. Набор ш = F[k].
Вентилятор имеет одну кромку с цветом d. Пусть (u, F [x + 1]) - это ребро. Обратите внимание, что Икс + 1 ≠ 1, поскольку (u, F [1]) неокрашено. Таким образом, d бесплатно на F[Икс]. Также, Икс ≠ k поскольку веер имеет длину k но существует F[Икс + 1]. Теперь мы можем показать, что после инверсии для каждого у ∈ {1, ..., Икс − 1, Икс + 1, ..., k}, цвет (F[у + 1], ты) свободен на F [y]. Обратите внимание, что до инверсии цвет (ты, F[у + 1]) не c или же d, поскольку c бесплатно на ты и (ты, F[Икс + 1]) имеет цвет d и раскраска действительна. Инверсия влияет только на окрашенные края. c или же d, поэтому выполняется (1).

F[Икс] может быть либо в CD_ты путь или нет. В противном случае инверсия не повлияет на набор свободных цветов на F[Икс], и d останется на нем свободным. Мы можем установить ш = F[Икс]. В противном случае мы можем показать, что F все еще фанат и d остается свободным на F[k]. С d был свободен на F[Икс] перед инверсией и F[Икс] находится на пути, F[Икс] является конечной точкой CD_ты путь и c будет бесплатно на F[Икс] после инверсии. Инверсия изменит цвет (ты, F[Икс + 1]) от d к c. Таким образом, поскольку c теперь бесплатно на F[Икс] и выполняется (1), F остается фанатом. Также, d остается свободным на F[k], поскольку F[k] не на CD_ты путь (предположим, что это так; поскольку d бесплатно на F[k], тогда это должна быть конечная точка пути, но ты и F[Икс] - конечные точки). Выбирать ш = F[k].

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

Раскраска края правильная

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

Алгоритм требует не более Δ + 1 цвета.

На данном этапе только цвета c и d используются. С ты смежно хотя бы с одним неокрашенным ребром и его степень ограничена Δ, хотя бы один цвет в {1, ..., Δ} доступен дляc. За d, F[k] может иметь степень Δ и не иметь неокрашенного смежного ребра. Таким образом, может потребоваться цвет Δ + 1.

Сложность

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