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

Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса для заданного корня (иногда называемого оптимальным ветвлением). Задача является ориентированным аналогом задачи о минимальном остовном дереве.

Алгоритм предложили независимо сначала Ён-Чин Чу и Чжен-Гон Лью (1965), а затем Джек Эдмондс (1967).

Алгоритм

Описание

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

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

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

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

Узлы $V^{\prime }$ — это узлы $V$, не принадлежащие $C$ плюс новый узел, обозначенный как $v_{C}$.

• Если $(u,v)$ является ребром в $E$ с $u\notin C$ и $v\in C$ (ребро с концом в цикле), тогда включаем в $E^{\prime }$ новое ребро $e=(u,v_{C})$ и определяем $w^{\prime }(e)=w(u,v)-w(\pi (v),v)$.
• Если $(u,v)$ является ребром в $E$ с $u\in C$ и $v\notin C$ (ребро с началом в цикле), то включаем в $E^{\prime }$ новое ребро $e=(v_{C},v)$ и определяем $w^{\prime }(e)=w(u,v)$.
• если $(u,v)$ является ребром в $E$ с $u\notin C$ и $v\notin C$ (ребро никак не связано с циклом), то включаем в $E^{\prime }$ новое ребро $e=(u,v)$ и определяем $w^{\prime }(e)=w(u,v)$.

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

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

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

Время работы

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

Ссылки

• Edmonds's algorithm ( edmonds-alg ) – реализация алгоритма Эдмондса на C с лицензией MIT. Этот источник использует реализацию Тарьяна для плотных графов.
• NetworkX, библиотека python, распространяемая по лицензии BSD, имеет реализацию алгоритма Эдмондса.
• (spanning-forest-builder 0.0.2) – Библиотека для построения ориентированных лесов минимального веса.