В теории графов , Алгоритм Эдмондса или Чу-Ль / Эдмондс алгоритмом является алгоритмом для нахождения остовного древовидного минимального веса (иногда называемый оптимум разветвления ). Это направленный аналог задачи о минимальном остовном дереве . Алгоритм был независимо предложен сначала Йоенг-Джин Чу и Ценг-Хонг Лю (1965), а затем Джеком Эдмондсом (1967).
Алгоритм
Описание
Алгоритм принимает на вход ориентированный граф где это набор узлов и - множество ориентированных ребер, выделенная вершина называется корнем , а действительный вес для каждого края . Возвращает обширное древообразование укорененный в минимального веса, где вес дерева определяется как сумма веса его краев, .
Алгоритм имеет рекурсивное описание. Позволять обозначают функцию, которая возвращает остовное древообразование с корнем минимального веса. Сначала удаляем любой край из чей пункт назначения . Мы также можем заменить любой набор параллельных ребер (ребра между одной и той же парой вершин в одном направлении) одним ребром с весом, равным минимальному весу этих параллельных ребер.
Теперь для каждого узла кроме корня, найдите ребро, входящее в наименьшего веса (с произвольным разрывом галстуков). Обозначим источник этого ребра через. Если набор ребер не содержит циклов, то .
Иначе, содержит хотя бы один цикл. Произвольно выберите один из этих циклов и назовите его. Теперь мы определяем новый взвешенный ориентированный граф в котором цикл "сворачивается" в один узел следующим образом:
Узлы узлы не в плюс новый узел, обозначенный.
- Если это край в с участием а также (край, входящий в цикл), затем включите в новый край , и определим .
- Если это край в с участием а также (край, уходящий от цикла), затем включите в новый край , и определим .
- Если это край в с участием а также (ребро, не имеющее отношения к циклу), затем включить в новый край , и определим .
Для каждого края в , мы помним, какое ребро в это соответствует.
Теперь найдите минимальную протяженность древовидности. из используя звонок . Состовное древообразование, каждая вершина имеет ровно одно входящее ребро. Позволять быть уникальным входящим краем для в . Это ребро соответствует ребру с участием . Удалить край из , разорвав цикл. Отметьте каждый оставшийся край в. Для каждого края вотметьте соответствующий край в . Теперь определим быть набором отмеченных краев, которые образуют минимальное остовное древообразование.
Заметьте, что определяется с точки зрения , с участием имеющий строго меньше вершин, чем . Находка для одновершинного графа тривиально (это просто сам), поэтому работа рекурсивного алгоритма гарантированно завершится.
Продолжительность
Время работы этого алгоритма . Более быстрая реализация алгоритма благодаря Роберту Тарьяну выполняется вовремядля разреженных графов идля плотных графов. Это так же быстро, как алгоритм Прима для неориентированного минимального остовного дерева. В 1986 году Габоу, Галил, Спенсер, Комптон и Тарджан разработали более быструю реализацию со временем выполнения..
Рекомендации
- Чу, YJ; Лю, Т.Х. (1965), «О кратчайшем древовидении ориентированного графа», Science Sinica , 14 : 1396–1400.
- Эдмондс, J. (1967), "Оптимальные разветвления", Журнал исследований Национального бюро стандарты Раздел B , 7 (4): 233-240, DOI : 10,6028 / jres.071b.032
- Tarjan, RE (1977), «Поиск оптимальных ветвлений», Сети , 7 : 25–35, DOI : 10.1002 / net.3230070103
- Камерини, PM; Fratta, L .; Maffioli, F. (1979), "Замечание о поиске оптимальных разветвлений", Сети , 9 (4): 309-312, DOI : 10.1002 / net.3230090403
- Гиббонс, Алан (1985), теория алгоритмических графов , издательство Кембриджского университета, ISBN 0-521-28881-9
- Gabow, HN; Галил, З .; Спенсер, Т .; Тарьян, RE (1986), "Эффективные алгоритмы для нахождения минимального остовного деревьев в неориентированный и ориентированных графов", Combinatorica , 6 (2): 109-122, DOI : 10.1007 / bf02579168
Внешние ссылки
- Алгоритм Эдмондса (edmonds-alg) - реализация алгоритма Эдмондса, написанная на C ++ и лицензированная по лицензии MIT . Этот источник использует реализацию Тарьяна для плотного графа.
- NetworkX, библиотека Python, распространяемая под BSD , имеет реализацию алгоритма Эдмондса .