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

Эта статья об оптимальном алгоритме ветвления. Алгоритм максимального соответствия см. в разделе Алгоритм Блоссома .

В графов теории алгоритм Эдмондса или алгоритм Чу-Лю/Эдмондса — это алгоритм поиска остовного древообразного дерева минимального веса (иногда называемого оптимальным ветвлением ). Это направленный аналог задачи о минимальном остовном дереве . Алгоритм был предложен независимо сначала Йонг-Джином Чу и Ценг-Хонг Лю (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)$ для одновершинного графа тривиально (это просто $D$ сам), поэтому рекурсивный алгоритм гарантированно завершится.

Время работы

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

Ссылки

• Чу, Ён Джин; Лю, Ценг-Хонг (1965), «О кратчайшем древовидении ориентированного графа» (PDF) , Scientia Sinica: Chung-kuo k`o hsueh , XIV (10): 1396–1400
• Эдмондс, Дж. (1967), «Оптимальные разветвления», Журнал исследований Национального бюро стандартов, раздел B , 71B (4): 233–240, doi : 10.6028/jres.071b.032
• Тарьян, Р.Э. (1977), «Нахождение оптимальных ветвей», Networks , 7 : 25–35, doi : 10.1002/net.3230070103
• Камерини, премьер-министр; Фратта, Л.; Маффиоли, Ф. (1979), «Заметки о поиске оптимальных разветвлений», Networks , 9 (4): 309–312, doi : 10.1002/net.3230090403
• Гиббонс, Алан (1985), Алгоритмическая теория графов , издательство Кембриджского университета, ISBN  0-521-28881-9
• Габоу, Гонконг ; Галил, З. ; Спенсер, Т.; Тарьян, Р.Э. (1986), «Эффективные алгоритмы поиска минимальных остовных деревьев в неориентированных и ориентированных графах», Combinatorica , 6 (2): 109–122, doi : 10.1007/bf02579168 , S2CID   35618095

Внешние ссылки

• Алгоритм Эдмондса ( edmonds-alg ) — реализация алгоритма Эдмондса, написанная на C++ и лицензированная по лицензии MIT . Этот источник использует реализацию Tarjan для плотного графа.
• NetworkX, библиотека Python , распространяемая под BSD , имеет реализацию алгоритма Эдмондса .