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

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

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

Алгоритм

Описание

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

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

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

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

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

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

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

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

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

Время работы

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

Примечания

Литература

Chu Y. J., Liu T. H. On the Shortest Arborescence of a Directed Graph // Science Sinica. — 1965. — Т. 14. — С. 1396–1400.
Edmonds J. Optimum Branchings // J. Res. Nat. Bur. Standards. — 1967. — Т. 71B. — С. 233–240. — doi:10.6028/jres.071b.032.
Tarjan R. E. Finding Optimum Branchings // Networks. — 1977. — Т. 7. — С. 25–35. — doi:10.1002/net.3230070103.
Camerini P.M., Fratta L., Maffioli F. A note on finding optimum branchings // Networks. — 1979. — Т. 9. — С. 309–312. — doi:10.1002/net.3230090403.
Alan Gibbons. Algorithmic Graph Theory. — Cambridge University press, 1985. — ISBN 0-521-28881-9.
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs // Combinatorica. — 1986. — Т. 6. — С. 109–122. — doi:10.1007/bf02579168.

Ссылки

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