Алгоритм Эдмондса
Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса для заданного корня (иногда называемого оптимальным ветвлением). Задача является ориентированным аналогом задачи о минимальном остовном дереве.
Алгоритм предложили независимо сначала Ён-Чин Чу и Чжен-Гон Лью (1965), а затем Джек Эдмондс (1967).
Алгоритм
Описание
Алгоритм принимает входной ориентированный граф D = ⟨ V , E ⟩ , где V является набором узлов, а E является набором ориентированных рёбер, выделенную вершину r ∈ V , называемую корнем, и вещественные значения весов w ( e ) для каждого ребра e ∈ E . Алгоритм возвращает остовное ориентированное корневое дерево A минимального веса с корнем в r , где вес корневого дерева определяется как сумма весов его рёбер, w ( A ) = ∑ e ∈ A w ( e ) > .
Алгоритм имеет рекурсивное описание. Пусть f ( D , r , w ) означает функцию, которая возвращает ориентированное корневое дерево с корнем в r минимального веса. Мы сначала удаляем любое ребро из E , концом которого служит r . Мы можем затем заменить любое множество параллельных рёбер (рёбер между одной и той же парой вершин в том же направлении) одним ребром с весом, равным минимальному весу этих параллельных рёбер.
Теперь для каждого узла v , отличного от корня, находим ребро, входящее в v , с минимальным весом. Обозначим источник этого ребра через π ( v ) . Если множество рёбер P = < ( π ( v ) , v ) ∣ v ∈ V ∖ < r >> >> не содержит каких-либо циклов, то f ( D , r , w ) = P .
В противном случае P содержит по меньшей мере один цикл. Произвольным образом выберем один из этих циклов и назовём его C . Мы теперь определяем новый взвешенный ориентированный граф D ′ = ⟨ V ′ , E ′ ⟩ =langle V^,E^ angle > , в котором цикл C «стянут» в один узел следующим образом:
Узлы V ′ > — это узлы V , не принадлежащие C плюс новый узел, обозначенный как v C > .
- Если ( u , v ) является ребром в E с u ∉ C и v ∈ C (ребро с концом в цикле), тогда включаем в E ′ > новое ребро e = ( u , v C ) )> и определяем w ′ ( e ) = w ( u , v ) − w ( π ( v ) , v ) (e)=w(u,v)-w(pi (v),v)> .
- Если ( u , v ) является ребром в E с u ∈ C и v ∉ C (ребро с началом в цикле), то включаем в E ′ > новое ребро e = ( v C , v ) ,v)> и определяем w ′ ( e ) = w ( u , v ) (e)=w(u,v)> .
- если ( u , v ) является ребром в E с u ∉ C и v ∉ C (ребро никак не связано с циклом), то включаем в E ′ > новое ребро e = ( u , v ) и определяем w ′ ( e ) = w ( u , v ) (e)=w(u,v)> .
Для каждого ребра в E ′ > мы запоминаем, какому ребру в E оно соответствует.
Теперь находим минимальное ориентированное корневое дерево A ′ > графа D ′ > путём вызова f ( D ′ , r , w ′ ) ,r,w^)> . Поскольку A ′ > является ориентированным корневым деревом, каждая вершина имеет в точности одно входящее ребро. Пусть ( u , v C ) )> будет единственным входящим ребром в v C > в A ′ > . Это ребро соответствует ребру ( u , v ) ∈ E с v ∈ C . Удалим ребро ( π ( v ) , v ) из C , разрывая цикл. Пометим каждое оставшееся ребро в C . Для каждого ребра в A ′ > пометим его соответствующее ребро в E . Теперь мы определим f ( D , r , w ) как набор помеченных рёбер, которые образуют минимальное ориентированное корневое дерево.
Заметим, что f ( D , r , w ) определена в терминах f ( D ′ , r , w ′ ) ,r,w^)> с D ′
Время работы
Время работы алгоритма — O ( E V ) . Более быстрая реализация алгоритма Роберта Тарьяна работает за время O ( E log V ) на разреженных графах и за время O ( V 2 ) )> на плотных графах. Это та же скорость, что и у алгоритма Прима для неориентированного минимального остовного дерева. В 1986 Габов, Галиль, Спенсер, Комптон и Тарьян предложили более быструю реализацию со временем работы O ( E + V log V ) .
Источник
Алгоритм Эдмондса
Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса для заданного корня (иногда называемого оптимальным ветвлением). Задача является ориентированным аналогом задачи о минимальном остовном дереве.
Алгоритм предложили независимо сначала Ён-Чин Чу и Чжен-Гон Лью (1965), а затем Джек Эдмондс (1967).
Алгоритм
Описание
Алгоритм принимает входной ориентированный граф D = ⟨ V , E ⟩ , где V является набором узлов, а E является набором ориентированных рёбер, выделенную вершину r ∈ V , называемую корнем, и вещественные значения весов w ( e ) для каждого ребра e ∈ E . Алгоритм возвращает остовное ориентированное корневое дерево A минимального веса с корнем в r , где вес корневого дерева определяется как сумма весов его рёбер, w ( A ) = ∑ e ∈ A w ( e ) > .
Алгоритм имеет рекурсивное описание. Пусть f ( D , r , w ) означает функцию, которая возвращает ориентированное корневое дерево с корнем в r минимального веса. Мы сначала удаляем все ребра из E , концом которых служит r . Мы можем затем заменить любое множество параллельных рёбер (рёбер между одной и той же парой вершин в том же направлении) одним ребром с весом, равным минимальному весу этих параллельных рёбер.
Теперь для каждого узла v , отличного от корня, находим ребро, входящее в v , с минимальным весом. Обозначим источник этого ребра через π ( v ) . Если множество рёбер P = < ( π ( v ) , v ) ∣ v ∈ V ∖ < r >> >> не содержит каких-либо циклов, то f ( D , r , w ) = P .
В противном случае P содержит по меньшей мере один цикл. Произвольным образом выберем один из этих циклов и назовём его C . Мы теперь определяем новый взвешенный ориентированный граф D ′ = ⟨ V ′ , E ′ ⟩ =langle V^,E^ angle > , в котором цикл C «стянут» в один узел следующим образом:
Узлы V ′ > — это узлы V , не принадлежащие C плюс новый узел, обозначенный как v C > .
- Если ( u , v ) является ребром в E с u ∉ C и v ∈ C (ребро с концом в цикле), тогда включаем в E ′ > новое ребро e = ( u , v C ) )> и определяем w ′ ( e ) = w ( u , v ) − w ( π ( v ) , v ) (e)=w(u,v)-w(pi (v),v)> .
- Если ( u , v ) является ребром в E с u ∈ C и v ∉ C (ребро с началом в цикле), то включаем в E ′ > новое ребро e = ( v C , v ) ,v)> и определяем w ′ ( e ) = w ( u , v ) (e)=w(u,v)> .
- если ( u , v ) является ребром в E с u ∉ C и v ∉ C (ребро никак не связано с циклом), то включаем в E ′ > новое ребро e = ( u , v ) и определяем w ′ ( e ) = w ( u , v ) (e)=w(u,v)> .
Для каждого ребра в E ′ > мы запоминаем, какому ребру в E оно соответствует.
Теперь находим минимальное ориентированное корневое дерево A ′ > графа D ′ > путём вызова f ( D ′ , r , w ′ ) ,r,w^)> . Поскольку A ′ > является ориентированным корневым деревом, каждая вершина имеет в точности одно входящее ребро. Пусть ( u , v C ) )> будет единственным входящим ребром в v C > в A ′ > . Это ребро соответствует ребру ( u , v ) ∈ E с v ∈ C . Удалим ребро ( π ( v ) , v ) из C , разрывая цикл. Пометим каждое оставшееся ребро в C . Для каждого ребра в A ′ > пометим его соответствующее ребро в E . Теперь мы определим f ( D , r , w ) как набор помеченных рёбер, которые образуют минимальное ориентированное корневое дерево.
Заметим, что f ( D , r , w ) определена в терминах f ( D ′ , r , w ′ ) ,r,w^)> с D ′
Время работы
Время работы алгоритма — O ( E V ) . Более быстрая реализация алгоритма Роберта Тарьяна работает за время O ( E log V ) на разреженных графах и за время O ( V 2 ) )> на плотных графах. Это та же скорость, что и у алгоритма Прима для неориентированного минимального остовного дерева. В 1986 Габов, Галиль, Спенсер, Комптон и Тарьян предложили более быструю реализацию со временем работы O ( E + V log V ) .
Источник