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

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

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

Алгоритм

Описание

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

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

Теперь для каждого узла ${\displaystyle v}$, отличного от корня, находим ребро, входящее в ${\displaystyle v}$, с минимальным весом. Обозначим источник этого ребра через ${\displaystyle \pi (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 (u,v)}$ является ребром в ${\displaystyle E}$ с ${\displaystyle u\notin C}$ и ${\displaystyle v\in C}$ (ребро с концом в цикле), тогда включаем в ${\displaystyle E^{\prime }}$ новое ребро ${\displaystyle e=(u,v_{C})}$ и определяем ${\displaystyle w^{\prime }(e)=w(u,v)-w(\pi (v),v)}$.
• Если ${\displaystyle (u,v)}$ является ребром в ${\displaystyle E}$ с ${\displaystyle u\in C}$ и ${\displaystyle v\notin C}$ (ребро с началом в цикле), то включаем в ${\displaystyle E^{\prime }}$ новое ребро ${\displaystyle e=(v_{C},v)}$ и определяем ${\displaystyle w^{\prime }(e)=w(u,v)}$.
• если ${\displaystyle (u,v)}$ является ребром в ${\displaystyle E}$ с ${\displaystyle u\notin C}$ и ${\displaystyle v\notin C}$ (ребро никак не связано с циклом), то включаем в ${\displaystyle E^{\prime }}$ новое ребро ${\displaystyle e=(u,v)}$ и определяем ${\displaystyle w^{\prime }(e)=w(u,v)}$.

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

Теперь находим минимальное ориентированное корневое дерево ${\displaystyle A^{\prime }}$ графа ${\displaystyle D^{\prime }}$ путём вызова ${\displaystyle f(D^{\prime },r,w^{\prime })}$. Поскольку ${\displaystyle A^{\prime }}$ является ориентированным корневым деревом, каждая вершина имеет в точности одно входящее ребро. Пусть ${\displaystyle (u,v_{C})}$ будет единственным входящим ребром в ${\displaystyle v_{C}}$ в ${\displaystyle A^{\prime }}$. Это ребро соответствует ребру ${\displaystyle (u,v)\in E}$ с ${\displaystyle v\in C}$. Удалим ребро ${\displaystyle (\pi (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 O(EV)}$. Более быстрая реализация алгоритма Роберта Тарьяна работает за время ${\displaystyle O(E\log V)}$ на разреженных графах и за время ${\displaystyle O(V^{2})}$ на плотных графах. Это та же скорость, что и у алгоритма Прима для неориентированного минимального остовного дерева. В 1986 Габов, Галиль, Спенсер, Комптон и Тарьян предложили более быструю реализацию со временем работы ${\displaystyle O(E+V\log V)}$.

Примечания

1. Алгоритм применим к нахождению минимального остовного леса с заданными корнями. Однако при поиске минимального остовного леса среди всех ${\displaystyle k}$-компонентных остовных лесов в сложности алгоритма возникает множитель ${\displaystyle C_{V}^{k}}$, отвечающий выбору подмножества вершин, назначаемых корнями. Это делает его малопригодным для такой задачи. Даже при построении минимального остовного дерева безотносительно корня алгоритм приходится применять ${\displaystyle V}$ раз, последовательно назначая каждую вершину корнем. Эффективный алгоритм поиска минимальных остовных лесов, решаюший проблему назначения корней, представлен в https://link.springer.com/article/10.1007/s10958-023-06666-w. Он строит последовательность минимальных ${\displaystyle k}$-компонентных остовных лесов для всех ${\displaystyle 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) – Библиотека для построения ориентированных лесов минимального веса.