Алгоритм Эдмондса - Edmonds' algorithm
Алгоритмы поиска по графам и деревьям |
---|
Списки |
похожие темы |
В теории графов , Алгоритм Эдмондса или Чу-Ль / Эдмондс алгоритмом является алгоритмом для нахождения остовного древовидного минимального веса (иногда называемый оптимум разветвления ). Это направленный аналог задачи о минимальном остовном дереве . Алгоритм был независимо предложен сначала Йоенг-Джин Чу и Ценг-Хонг Лю (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 ; Галил, З .; Спенсер, Т .; Tarjan, RE (1986), «Эффективные алгоритмы для поиска минимальных остовных деревьев в неориентированных и ориентированных графах», Combinatorica , 6 (2): 109–122, doi : 10.1007 / bf02579168
Внешние ссылки
- Алгоритм Эдмондса (edmonds-alg) - реализация алгоритма Эдмондса, написанная на C ++ и лицензированная по лицензии MIT . Этот источник использует реализацию Тарьяна для плотного графа.
- NetworkX, библиотека Python, распространяемая под BSD , имеет реализацию алгоритма Эдмондса .