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

Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса для заданного корня (иногда называемого оптимальным ветвлением). Задача является ориентированным аналогом задачи о минимальном остовном дереве.

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

Алгоритм

Описание

Алгоритм принимает входной ориентированный граф D = ⟨ V , E ⟩ {displaystyle D=langle V,E angle } , где V {displaystyle V} является набором узлов, а E {displaystyle E} является набором ориентированных рёбер, выделенную вершину r ∈ V {displaystyle rin V} , называемую корнем, и вещественные значения весов w ( e ) {displaystyle w(e)} для каждого ребра e ∈ E {displaystyle ein E} . Алгоритм возвращает остовное ориентированное корневое дерево A {displaystyle A} минимального веса с корнем в r {displaystyle r} , где вес корневого дерева определяется как сумма весов его рёбер, w ( A ) = ∑ e ∈ A w ( e ) {displaystyle w(A)=sum _{ein A}{w(e)}} .

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

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

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

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

• Если ( u , v ) {displaystyle (u,v)} является ребром в E {displaystyle E} с u ∉ C {displaystyle u otin C} и v ∈ C {displaystyle vin C} (ребро с концом в цикле), тогда включаем в E ′ {displaystyle E^{prime }} новое ребро e = ( u , v C ) {displaystyle e=(u,v_{C})} и определяем w ′ ( e ) = w ( u , v ) − w ( π ( v ) , v ) {displaystyle w^{prime }(e)=w(u,v)-w(pi (v),v)} .
• Если ( u , v ) {displaystyle (u,v)} является ребром в E {displaystyle E} с u ∈ C {displaystyle uin C} и v ∉ C {displaystyle v otin C} (ребро с началом в цикле), то включаем в E ′ {displaystyle E^{prime }} новое ребро e = ( v C , v ) {displaystyle e=(v_{C},v)} и определяем w ′ ( e ) = w ( u , v ) {displaystyle w^{prime }(e)=w(u,v)} .
• если ( u , v ) {displaystyle (u,v)} является ребром в E {displaystyle E} с u ∉ C {displaystyle u otin C} и v ∉ C {displaystyle v otin C} (ребро никак не связано с циклом), то включаем в E ′ {displaystyle E^{prime }} новое ребро e = ( u , v ) {displaystyle e=(u,v)} и определяем w ′ ( e ) = w ( u , v ) {displaystyle w^{prime }(e)=w(u,v)} .

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

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

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

Время работы

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