Алгоритм Эдмондса - Edmonds algorithm

В теория графов, Алгоритм Эдмондса или же Алгоритм Чу – Лю / Эдмондса является алгоритм для поиска охватывающий древообразование минимального веса (иногда называемый оптимальное ветвление).Это направленный аналог минимальное остовное дерево Алгоритм был независимо предложен сначала Йоенг-Джин Чу и Ценг-Хонг Лю (1965), а затем Джек Эдмондс (1967).

Алгоритм

Описание

Алгоритм принимает на вход ориентированный граф ${ Displaystyle D = langle V, E rangle}$ куда ${ displaystyle V}$ это набор узлов и ${ displaystyle E}$ - множество направленных ребер, выделенная вершина ${ displaystyle r in V}$ называется корень, и действительный вес ${ Displaystyle ш (е)}$ для каждого края ${ displaystyle e in E}$ . Он возвращает охват древообразование ${ displaystyle A}$ укорененный в ${ displaystyle r}$ минимального веса, где вес древесного ствола определяется как сумма веса его краев, ${ Displaystyle ш (А) = сумма _ {е в А} {ш (е)}}$ .

Алгоритм имеет рекурсивное описание. ${ displaystyle f (D, r, w)}$ обозначают функцию, которая возвращает остовное древообразование с корнем ${ displaystyle r}$ минимального веса.Сначала удаляем края с ${ displaystyle E}$ чей пункт назначения ${ displaystyle r}$ Мы также можем заменить любой набор параллельных ребер (ребра между одной парой вершин в одном направлении) одним ребром с весом, равным минимальному весу этих параллельных ребер.

Теперь для каждого узла ${ displaystyle v}$ кроме корня, найдите ребро, входящее в ${ displaystyle v}$ наименьшего веса (с произвольным разрывом связей) .Обозначим источник этого ребра ${ Displaystyle пи (v)}$ .Если набор ребер ${ Displaystyle P = {( pi (v), v) mid v in V setminus {r } }}$ не содержит циклов, то ${ displaystyle f (D, r, w) = P}$ .

Иначе, ${ displaystyle P}$ содержит хотя бы один цикл. Произвольно выберите один из этих циклов и назовите его ${ displaystyle C}$ .Теперь мы определяем новый взвешенный ориентированный граф ${ Displaystyle D ^ { prime} = langle V ^ { prime}, E ^ { prime} rangle}$ в котором цикл ${ displaystyle C}$ "сворачивается" в один узел следующим образом:

Узлы ${ Displaystyle V ^ { prime}}$ узлы ${ displaystyle V}$ не в ${ displaystyle C}$ плюс новый узел обозначен ${ displaystyle v_ {C}}$ .

Если ${ Displaystyle (и, v)}$ это край в ${ displaystyle E}$ с ${ displaystyle u notin C}$ и ${ displaystyle v in C}$ (край, входящий в цикл), затем включите в ${ displaystyle E ^ { prime}}$ новый край ${ Displaystyle е = (и, v_ {C})}$ , и определим ${ Displaystyle ш ^ { простое} (е) = вес (и, v) -w ( пи (v), v)}$ .
Если ${ Displaystyle (и, v)}$ это край в ${ displaystyle E}$ с ${ displaystyle u in C}$ и ${ displaystyle v notin C}$ (край, уходящий от цикла), затем включите ${ displaystyle E ^ { prime}}$ новый край ${ Displaystyle е = (v_ {C}, v)}$ , и определим ${ Displaystyle ш ^ { простое} (е) = вес (и, v)}$ .
Если ${ Displaystyle (и, v)}$ это край в ${ displaystyle E}$ с ${ displaystyle u notin C}$ и ${ displaystyle v notin C}$ (ребро, не связанное с циклом), затем включить в ${ displaystyle E ^ { prime}}$ новый край ${ Displaystyle е = (и, v)}$ , и определим ${ Displaystyle ш ^ { простое} (е) = вес (и, v)}$ .

Для каждого края в ${ displaystyle E ^ { prime}}$ , мы помним, какое ребро в ${ displaystyle E}$ это соответствует.

Теперь найдите минимальный охват древовидности ${ displaystyle A ^ { prime}}$ из ${ Displaystyle D ^ { prime}}$ используя звонок ${ displaystyle f (D ^ { prime}, r, w ^ { prime})}$ .С ${ displaystyle A ^ { prime}}$ остовное древообразование, каждая вершина имеет ровно одно входящее ребро. ${ displaystyle (и, v_ {C})}$ быть уникальным входящим краем для ${ displaystyle v_ {C}}$ в ${ displaystyle A ^ { prime}}$ Это ребро соответствует ребру ${ displaystyle (u, v) in E}$ с ${ displaystyle v in C}$ .Удалите край ${ Displaystyle ( пи (v), v)}$ из ${ displaystyle C}$ , прерывая цикл. Отметьте каждое оставшееся ребро в ${ displaystyle C}$ .Для каждого края в ${ displaystyle A ^ { prime}}$ отметьте соответствующий край в ${ displaystyle E}$ .Теперь определим ${ displaystyle f (D, r, w)}$ быть набором отмеченных краев, которые образуют минимальное остовное древообразование.

Заметьте, что ${ displaystyle f (D, r, w)}$ определяется в терминах ${ displaystyle f (D ^ { prime}, r, w ^ { prime})}$ , с ${ Displaystyle D ^ { prime}}$ имеющий строго меньше вершин, чем ${ displaystyle D}$ . обнаружение ${ displaystyle f (D, r, w)}$ для одновершинного графа тривиально (это просто ${ displaystyle D}$ сам), поэтому рекурсивный алгоритм гарантированно завершится.

Продолжительность

Время работы этого алгоритма ${ displaystyle O (EV)}$ . Более быстрая реализация алгоритма за счет Роберт Тарджан бежит во времени ${ Displaystyle О (Е журнал V)}$ за разреженные графики и ${ displaystyle O (V ^ {2})}$ для плотных графов. Это так быстро, как Алгоритм Прима для неориентированного минимального остовного дерева. В 1986 году Габоу, Галил, Спенсер, Комптон и Тарджан разработали более быструю реализацию со временем выполнения. ${ Displaystyle О (Е + В журнал V)}$ .

внешняя ссылка

Алгоритм Эдмондса (edmonds-alg) - Реализация алгоритма Эдмондса, написанного на C ++ и под лицензией Лицензия MIT. Этот источник использует реализацию Тарьяна для плотного графа.
NetworkX, a питон библиотека распространяется под BSD, имеет реализацию Алгоритм Эдмондса.

Алгоритм Эдмондса - Edmonds algorithm

Содержание