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

В теории графов алгоритм Эдмондса или алгоритм Чу–Лю/Эдмондса — это алгоритм для поиска остовного дерева минимального веса (иногда называемого оптимальным ветвлением ). ^[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 А}$${\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 \пи (v)}$${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$${\displaystyle f(D,r,w)=P}$

В противном случае содержит по крайней мере один цикл. Произвольно выберем один из этих циклов и назовем его . Теперь мы определим новый взвешенный ориентированный граф , в котором цикл «сжимается» в один узел следующим образом:${\displaystyle P}$${\displaystyle С}$${\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 D}$

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

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

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