Алгоритм Эдмондса
Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева[англ.] минимального веса для заданного корня (иногда называемого оптимальным ветвлением).Задача является ориентированным аналогом задачи о минимальном остовном дереве.
Алгоритм предложили независимо сначала Ён-Чин Чу и Чжен-Гон Лью (1965), а затем Джек Эдмондс (1967).
Алгоритм
Описание
Алгоритм принимает входной ориентированный граф , где является набором узлов, а является набором ориентированных рёбер, выделенную вершину , называемую корнем, и вещественные значения весов для каждого ребра .Алгоритм возвращает остовное ориентированное корневое дерево[англ.] минимального веса с корнем в , где вес корневого дерева определяется как сумма весов его рёбер, .
Алгоритм имеет рекурсивное описание.Пусть означает функцию, которая возвращает ориентированное корневое дерево с корнем в минимального веса.Мы сначала удаляем все ребра из , концом которых служит .Мы можем затем заменить любое множество параллельных рёбер (рёбер между одной и той же парой вершин в том же направлении) одним ребром с весом, равным минимальному весу этих параллельных рёбер.
Теперь для каждого узла , отличного от корня, находим ребро, входящее в , с минимальным весом.Обозначим источник этого ребра через .Если множество рёбер не содержит каких-либо циклов, то .
В противном случае содержит по меньшей мере один цикл.Произвольным образом выберем один из этих циклов и назовём его .Мы теперь определяем новый взвешенный ориентированный граф , в котором цикл «стянут» в один узел следующим образом:
Узлы — это узлы , не принадлежащие плюс новый узел, обозначенный как .
- Если является ребром в с и (ребро с концом в цикле), тогда включаем в новое ребро и определяем .
- Если является ребром в с и (ребро с началом в цикле), то включаем в новое ребро и определяем .
- если является ребром в с и (ребро никак не связано с циклом), то включаем в новое ребро и определяем .
Для каждого ребра в мы запоминаем, какому ребру в оно соответствует.
Теперь находим минимальное ориентированное корневое дерево графа путём вызова .Поскольку является ориентированным корневым деревом, каждая вершина имеет в точности одно входящее ребро.Пусть будет единственным входящим ребром в в .Это ребро соответствует ребру с .Удалим ребро из , разрывая цикл.Пометим каждое оставшееся ребро в .Для каждого ребра в пометим его соответствующее ребро в .Теперь мы определим как набор помеченных рёбер, которые образуют минимальное ориентированное корневое дерево.
Заметим, что определена в терминах с , имеющим строго меньшее число вершин, чем у . Нахождение для графа, состоящего из отдельной вершины, тривиально, так что рекурсивный алгоритм гарантированно завершится.
Время работы
Время работы алгоритма — . Более быстрая реализация алгоритма Роберта Тарьяна работает за время на разреженных графах и за время на плотных графах. Это та же скорость, что и у алгоритма Прима для неориентированного минимального остовного дерева. В 1986 Габов, Галиль, Спенсер, Комптон и Тарьян предложили более быструю реализацию со временем работы .
Примечания
Литература
Ссылки
- Edmonds's algorithm ( edmonds-alg ) – реализация алгоритма Эдмондса на C++ с лицензией MIT. Этот источник использует реализацию Тарьяна для плотных графов.
- NetworkX, библиотека python, распространяемая по лицензии BSD, имеет реализацию алгоритма Эдмондса.