Алгоритм Эдмондса

Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного Шаблон:Не переведено 5 минимального веса для заданного корня (иногда называемого оптимальным ветвлением)^[1]. Задача является ориентированным аналогом задачи о минимальном остовном дереве.

Алгоритм предложили независимо сначала Ён-Чин Чу и Чжен-Гон Лью (1965), а затем Джек Эдмондс (1967).

Алгоритм

Описание

Алгоритм принимает входной ориентированный граф $D = ⟨ V, E ⟩$ , где $V$ является набором узлов, а $E$ является набором ориентированных рёбер, выделенную вершину $r \in V$ , называемую корнем, и вещественные значения весов $w (e)$ для каждого ребра $e \in E$ . Алгоритм возвращает остовное Шаблон:Не переведено 5 $A$ минимального веса с корнем в $r$ , где вес корневого дерева определяется как сумма весов его рёбер, $w (A) = \sum_{e \in A} w (e)$ .

Алгоритм имеет рекурсивное описание. Пусть $f (D, r, w)$ означает функцию, которая возвращает ориентированное корневое дерево с корнем в $r$ минимального веса. Мы сначала удаляем все ребра из $E$ , концом которых служит $r$ . Мы можем затем заменить любое множество параллельных рёбер (рёбер между одной и той же парой вершин в том же направлении) одним ребром с весом, равным минимальному весу этих параллельных рёбер.

Теперь для каждого узла $v$ , отличного от корня, находим ребро, входящее в $v$ , с минимальным весом. Обозначим источник этого ребра через $π (v)$ . Если множество рёбер $P = {(π (v), v) ∣ v \in V ∖ {r}}$ не содержит каких-либо циклов, то $f (D, r, w) = P$ .

В противном случае $P$ содержит по меньшей мере один цикл. Произвольным образом выберем один из этих циклов и назовём его $C$ . Мы теперь определяем новый взвешенный ориентированный граф $D^{'} = ⟨ V^{'}, E^{'} ⟩$ , в котором цикл $C$ «стянут» в один узел следующим образом:

Узлы $V^{'}$ — это узлы $V$ , не принадлежащие $C$ плюс новый узел, обозначенный как $v_{C}$ .

Если $(u, v)$ является ребром в $E$ с $u \notin C$ и $v \in C$ (ребро с концом в цикле), тогда включаем в $E^{'}$ новое ребро $e = (u, v_{C})$ и определяем $w^{'} (e) = w (u, v) - w (π (v), v)$ .
Если $(u, v)$ является ребром в $E$ с $u \in C$ и $v \notin C$ (ребро с началом в цикле), то включаем в $E^{'}$ новое ребро $e = (v_{C}, v)$ и определяем $w^{'} (e) = w (u, v)$ .
если $(u, v)$ является ребром в $E$ с $u \notin C$ и $v \notin C$ (ребро никак не связано с циклом), то включаем в $E^{'}$ новое ребро $e = (u, v)$ и определяем $w^{'} (e) = w (u, v)$ .

Для каждого ребра в $E^{'}$ мы запоминаем, какому ребру в $E$ оно соответствует.

Теперь находим минимальное ориентированное корневое дерево $A^{'}$ графа $D^{'}$ путём вызова $f (D^{'}, r, w^{'})$ . Поскольку $A^{'}$ является ориентированным корневым деревом, каждая вершина имеет в точности одно входящее ребро. Пусть $(u, v_{C})$ будет единственным входящим ребром в $v_{C}$ в $A^{'}$ . Это ребро соответствует ребру $(u, v) \in E$ с $v \in C$ . Удалим ребро $(π (v), v)$ из $C$ , разрывая цикл. Пометим каждое оставшееся ребро в $C$ . Для каждого ребра в $A^{'}$ пометим его соответствующее ребро в $E$ . Теперь мы определим $f (D, r, w)$ как набор помеченных рёбер, которые образуют минимальное ориентированное корневое дерево.

Заметим, что $f (D, r, w)$ определена в терминах $f (D^{'}, r, w^{'})$ с $D^{'}$ , имеющим строго меньшее число вершин, чем у $D$ . Нахождение $f (D, r, w)$ для графа, состоящего из отдельной вершины, тривиально, так что рекурсивный алгоритм гарантированно завершится.

Время работы

Время работы алгоритма — $O (E V)$ . Более быстрая реализация алгоритма Роберта Тарьяна работает за время $O (E \log V)$ на разреженных графах и за время $O (V^{2})$ на плотных графах. Это та же скорость, что и у алгоритма Прима для неориентированного минимального остовного дерева. В 1986 Габов, Галиль, Спенсер, Комптон и Тарьян предложили более быструю реализацию со временем работы $O (E + V \log V)$ .

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Edmonds's algorithm ( edmonds-alg ) – реализация алгоритма Эдмондса на C++ с лицензией MIT. Этот источник использует реализацию Тарьяна для плотных графов.
NetworkX, библиотека python, распространяемая по лицензии BSD, имеет реализацию алгоритма Эдмондса.
(spanning-forest-builder 0.0.2) – Библиотека для построения ориентированных лесов минимального веса.

Шаблон:Rq

↑ Алгоритм применим к нахождению минимального остовного леса с заданными корнями. Однако при поиске минимального остовного леса среди всех $k$ -компонентных остовных лесов в сложности алгоритма возникает множитель $C_{V}^{k}$ , отвечающий выбору подмножества вершин, назначаемых корнями. Это делает его малопригодным для такой задачи. Даже при построении минимального остовного дерева безотносительно корня алгоритм приходится применять $V$ раз, последовательно назначая каждую вершину корнем. Эффективный алгоритм поиска минимальных остовных лесов, решаюший проблему назначения корней, представлен в https://link.springer.com/article/10.1007/s10958-023-06666-w. Он строит последовательность минимальных $k$ -компонентных остовных лесов для всех $k$ вплоть до остовного минимального дерева. Алгоритм Чу — Лью/Эдмондса является его составной частью.

[1] Алгоритм применим к нахождению минимального остовного леса с заданными корнями. Однако при поиске минимального остовного леса среди всех $k$ -компонентных остовных лесов в сложности алгоритма возникает множитель $C_{V}^{k}$ , отвечающий выбору подмножества вершин, назначаемых корнями. Это делает его малопригодным для такой задачи. Даже при построении минимального остовного дерева безотносительно корня алгоритм приходится применять $V$ раз, последовательно назначая каждую вершину корнем. Эффективный алгоритм поиска минимальных остовных лесов, решаюший проблему назначения корней, представлен в https://link.springer.com/article/10.1007/s10958-023-06666-w. Он строит последовательность минимальных $k$ -компонентных остовных лесов для всех $k$ вплоть до остовного минимального дерева. Алгоритм Чу — Лью/Эдмондса является его составной частью.

[1]

Алгоритм Эдмондса

Содержание