Алгоритм Эдмондса - 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

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