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

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

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

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