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

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

Примечания

Литература

Ссылки

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