Алгоритм Эдмондса (Glikjnmb |;bku;vg)

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

Алгоритм предложили независимо сначала Ён-Чин Чу и Чжен-Гон Лью (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)$ .

Примечания

↑ Алгоритм применим к нахождению минимального остовного леса с заданными корнями. Однако при поиске минимального остовного леса среди всех $k$ -компонентных остовных лесов в сложности алгоритма возникает множитель $C_{V}^{k}$ , отвечающий выбору подмножества вершин, назначаемых корнями. Это делает его малопригодным для такой задачи. Даже при построении минимального остовного дерева безотносительно корня алгоритм приходится применять $V$ раз, последовательно назначая каждую вершину корнем. Эффективный алгоритм поиска минимальных остовных лесов, решаюший проблему назначения корней, представлен в https://link.springer.com/article/10.1007/s10958-023-06666-w. Он строит последовательность минимальных $k$ -компонентных остовных лесов для всех $k$ вплоть до остовного минимального дерева. Алгоритм Чу — Лью/Эдмондса является его составной частью.

Литература

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.
Buslov V.A. Algorithm for Sequential Construction of Spanning Minimal Directed Forests // Journal of Mathematical Sciences. — 2023. — Т. 275. — С. 117–129. — doi:10.1007/s10958-023-06666-w.

Ссылки

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

[1] Алгоритм применим к нахождению минимального остовного леса с заданными корнями. Однако при поиске минимального остовного леса среди всех $k$ -компонентных остовных лесов в сложности алгоритма возникает множитель $C_{V}^{k}$ , отвечающий выбору подмножества вершин, назначаемых корнями. Это делает его малопригодным для такой задачи. Даже при построении минимального остовного дерева безотносительно корня алгоритм приходится применять $V$ раз, последовательно назначая каждую вершину корнем. Эффективный алгоритм поиска минимальных остовных лесов, решаюший проблему назначения корней, представлен в https://link.springer.com/article/10.1007/s10958-023-06666-w. Он строит последовательность минимальных $k$ -компонентных остовных лесов для всех $k$ вплоть до остовного минимального дерева. Алгоритм Чу — Лью/Эдмондса является его составной частью.

[1]