Русская Википедия:Алгоритм Эдмондса
Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного Шаблон:Не переведено 5 минимального веса для заданного корня (иногда называемого оптимальным ветвлением). Задача является ориентированным аналогом задачи о минимальном остовном дереве.
Алгоритм предложили независимо сначала Ён-Чин Чу и Чжен-Гон Лью (1965), а затем Джек Эдмондс (1967).
Алгоритм
Описание
Алгоритм принимает входной ориентированный граф <math>D = \langle V, E \rangle</math>, где <math>V</math> является набором узлов, а <math>E</math> является набором ориентированных рёбер, выделенную вершину <math>r \in V</math>, называемую корнем, и вещественные значения весов <math>w(e)</math> для каждого ребра <math>e \in E</math>. Алгоритм возвращает остовное Шаблон:Не переведено 5 <math>A</math> минимального веса с корнем в <math>r</math>, где вес корневого дерева определяется как сумма весов его рёбер, <math>w(A) = \sum_{e \in A}{w(e)}</math>.
Алгоритм имеет рекурсивное описание. Пусть <math>f(D, r, w)</math> означает функцию, которая возвращает ориентированное корневое дерево с корнем в <math>r</math> минимального веса. Мы сначала удаляем все ребра из <math>E</math>, концом которых служит <math>r</math>. Мы можем затем заменить любое множество параллельных рёбер (рёбер между одной и той же парой вершин в том же направлении) одним ребром с весом, равным минимальному весу этих параллельных рёбер.
Теперь для каждого узла <math>v</math>, отличного от корня, находим ребро, входящее в <math>v</math>, с минимальным весом. Обозначим источник этого ребра через <math>\pi(v)</math>. Если множество рёбер <math>P = \{(\pi(v),v) \mid v \in V \setminus \{ r \} \}</math> не содержит каких-либо циклов, то <math>f(D,r,w) = P</math>.
В противном случае <math>P</math> содержит по меньшей мере один цикл. Произвольным образом выберем один из этих циклов и назовём его <math>C</math>. Мы теперь определяем новый взвешенный ориентированный граф <math>D^\prime = \langle V^\prime, E^\prime \rangle</math>, в котором цикл <math>C</math> «стянут» в один узел следующим образом:
Узлы <math>V^\prime</math> — это узлы <math>V</math>, не принадлежащие <math>C</math> плюс новый узел, обозначенный как <math>v_C</math>.
- Если <math>(u,v)</math> является ребром в <math>E</math> с <math>u\notin C</math> и <math>v\in C</math> (ребро с концом в цикле), тогда включаем в <math>E^\prime</math> новое ребро <math>e = (u, v_C)</math> и определяем <math>w^\prime(e) = w(u,v) - w(\pi(v),v)</math>.
- Если <math>(u,v)</math> является ребром в <math>E</math> с <math>u\in C</math> и <math>v\notin C</math> (ребро с началом в цикле), то включаем в <math>E^\prime</math> новое ребро <math>e = (v_C, v)</math> и определяем <math>w^\prime(e) = w(u,v) </math>.
- если <math>(u,v)</math> является ребром в <math>E</math> с <math>u\notin C</math> и <math>v\notin C</math> (ребро никак не связано с циклом), то включаем в <math>E^\prime</math> новое ребро <math>e = (u, v)</math> и определяем <math>w^\prime(e) = w(u,v) </math>.
Для каждого ребра в <math>E^\prime</math> мы запоминаем, какому ребру в <math>E</math> оно соответствует.
Теперь находим минимальное ориентированное корневое дерево <math>A^\prime</math> графа <math>D^\prime</math> путём вызова <math>f(D^\prime, r,w^\prime)</math>. Поскольку <math>A^\prime</math> является ориентированным корневым деревом, каждая вершина имеет в точности одно входящее ребро. Пусть <math>(u, v_C)</math> будет единственным входящим ребром в <math>v_C</math> в <math>A^\prime</math>. Это ребро соответствует ребру <math>(u,v) \in E</math> с <math>v \in C</math>. Удалим ребро <math>(\pi(v),v)</math> из <math>C</math>, разрывая цикл. Пометим каждое оставшееся ребро в <math>C</math>. Для каждого ребра в <math>A^\prime</math> пометим его соответствующее ребро в <math>E</math>. Теперь мы определим <math>f(D, r, w)</math> как набор помеченных рёбер, которые образуют минимальное ориентированное корневое дерево.
Заметим, что <math>f(D, r, w)</math> определена в терминах <math>f(D^\prime, r, w^\prime)</math> с <math>D^\prime</math>, имеющим строго меньшее число вершин, чем у <math>D</math>. Нахождение <math>f(D, r, w)</math> для графа, состоящего из отдельной вершины, тривиально, так что рекурсивный алгоритм гарантированно завершится.
Время работы
Время работы алгоритма — <math>O(EV)</math>. Более быстрая реализация алгоритма Роберта Тарьяна работает за время <math>O(E \log V)</math> на разреженных графах и за время <math>O(V^2)</math> на плотных графах. Это та же скорость, что и у алгоритма Прима для неориентированного минимального остовного дерева. В 1986 Габов, Галиль, Спенсер, Комптон и Тарьян предложили более быструю реализацию со временем работы <math>O(E + V \log V)</math>.
Примечания
Литература
Ссылки
- Edmonds's algorithm ( edmonds-alg ) – реализация алгоритма Эдмондса на C++ с лицензией MIT. Этот источник использует реализацию Тарьяна для плотных графов.
- NetworkX, библиотека python, распространяемая по лицензии BSD, имеет реализацию алгоритма Эдмондса.
