Едмондсов алгоритам

Овај чланак је о алгоритму оптималног гранања. За алгоритам максималног поклапања погледајте Алгоритам максималног упаривања.

У теорији графова, грани математике, Едмондсов алгоритам или Чу-Лиу/Едмондсов алгоритам је алгоритам за проналажење максималног или минималног оптималног гранања. Овај алгоритам је сличан проблему минималног разапињућег стабла, који се тиче неусмерених графова. Ипак, када су чворови повезани усмереним гранама са тежинским коефицијентима, алгоритам минималног разапињућег стабла се не може користити.

Алгоритам оптималног гранања су предложили независно Јенг-јин Чу (Yoeng-jin Chu) и Ценг-хонг Лиу (Tseng-hong Liu) 1965. године, а затим и Едмондс 1967. године. За проналазак путање максималне дужине, узима се грана са највећим тежинским коефицијентом и повезују се одговарајућа два чвора, затим се узима следећа грана по тежини, итд. Ако одабрана грана прави петљу, уклања се и бира се наредна грана. Проналазак путање минималне дужине се врши аналогно, одабиром гране са најмањом тежином.

Сложеност алгоритма

Сложеност овог алгоритма је реда $O(EV)$. Постоји и бржа имплементација, коју је предложио Роберт Тарјан. Сложеност тог алгоритма је реда $O(E\log V)$ за ретки граф, а реда $O(V^{2})$ за збијени граф. Тај алгоритам је брз колико и Примов алгоритам за минимално повезујуће стабло. 1986. године , Габов (Gabow), Галил (Galil), Спенсер (Spencer), и Тарјан (Tarjan) су направили бржу имплементацију, реда $O(E+V\log V)$.

Алгоритам

Опис

Алгоритам је рекурзиван. Са $f$ је означена функција која за дати усмерени граф са тежинским коефицијентима $D$ и чвором $r$ који представља корен, враћа повезујуће стабло минималне тежине, са кореном у $r$.

За дати усмерени граф $D$ са тежинским коефицијентима и корен $r$ заменимо било који скуп паралелних грана (грана између два иста чвора, у истом правцу) једном граном са тежином једнаком најмањој тежини у датом скупу грана.

Даље, за сваки чвор $v$ различит од $r$, обележимо долазећу грану најмање тежине. Означимо други крај те гране са $\pi (v)$. Грана је тако означена са $(\pi (v),v)$, а придружена тежина са $w(\pi (v),v)$. Ако обележене гране формирају стабло најкраће путање, $f(D)$ је то стабло. У супротном, скуп обележених грана формира бар једну петљу. Нека је $C$ једна од ових петљи (насумично одабрана). Дефинишемо усмерени граф са тежинским коефицијентима, $D^{\prime }$ и кореном у $r^{\prime }$ према следећем упутству: чворови $D^{\prime }$ су чворови $D$ који се не налазе у $C$ и нови чвор је означен са $v_{C}$.

Ако је $(u,v)$ грана у $D$ где је $u\notin C$ и $v\in C$, онда треба укључити у $D^{\prime }$ грану $e=(u,v_{C})$, и дефинисати $w(e)=w(u,v)-w(\pi (v),v)$.

Ако је $(u,v)$ грана у $D$ где је $u\in C$ и $v\notin C$, онда треба укључити у $D^{\prime }$ грану $e=(v_{C},v)$, и дефинисати $w(e)=w(u,v)$.

Ако је $(u,v)$ грана у $D$ где је $u\notin C$ и $v\notin C$, онда треба укључити у $D^{\prime }$ грану $e=(u,v)$, и дефинисати $w(e)=w(u,v)$.

У $D^{\prime }$ се не укључује ниједна друга грана.

Корен $r^{\prime }$ стабла $D^{\prime }$ је корен $r$ стабла $D$.

Позивом функције $f(D^{\prime })$, налази се стабло најкраће путање за $D^{\prime }$. Прво, означе се у стаблу $D$ све гране које су и у $D^{\prime }$, а које су означене у стаблу најкраће путање(СНП) за $D^{\prime }$. Такође, означе се у $D$ све гране из $C$. Даље, претпоставимо да је у СНП за $D^{\prime }$, (јединствена) долазећа грана у $v_{C}$ $(u,v_{C})$. Та грана долази из неког пара $(u,v)$ где је $u\notin C$ и $v\in C$. Треба обрисати $(\pi (v),v)$ и означити $(u,v)$. Такође, за сваку означену $(v_{C},v)$ у СНП за $D^{\prime }$ која потиче од гране $(u,v)$ у $D$ где је $u\in C$ и $v\notin C$, означити грану $(u,v)$. Сада скуп означених грана формира СНП, што је повратна вредност $f(D)$.

Имплементација

Нека је BV скуп чворова и BE скуп грана. Нека је v чвор, а e грана са највећом позитивном тежином која повезује v. C_i је петља. G₀ = (V₀,E₀) је оригинални дијаграм. u_i је заменски чвор за C_i.

$BV\leftarrow BE\leftarrow \varnothing$
i=0

A:
if $BV=V_{i}$ then goto B
for неки чвор $v\notin BV$ and $v\in V_{i}$ {
   $BV\leftarrow BV\cup \lbrace v\rbrace$
   нађи грану $e=(x,v)$ тако да w(e) = max{ w(y,v)|(y,v) $\in$ Ei}
   if w(e) ≤ 0 then goto A
}
if $BE\cup \lbrace e\rbrace$ садржи петљу {
   i=i+1
   конструиши $G_{i}$ сажимајући $C_{i}$ на $u_{i}$
   измени BE, BV и тежинске коефицијенте
}
$BE\leftarrow BE\cup {e}$
goto A

B:
while i ≠ 0 {
   реконструиши $G_{i-1}$ и преименуј неке гране у BE
   if $u_{i}$ је био корен излазног стабла BE {
       $BE\leftarrow BE\cup \lbrace e|e\in C_{i}$ and $e\neq e_{0}^{i}\rbrace$
   }else{
       $BE\leftarrow BE\cup \lbrace e|e\in C_{i}$ and $e\neq {\tilde {e}}_{i}\rbrace$
   }
   i=i-1
}
Максимална тежина гране  = $\sum _{e\in BE}w(e)$

Спољашње везе

• The Directed Minimum Spanning Tree Problem Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.
• Edmonds's algorithm (edmonds-alg ) – An open source implementation of Edmonds's algorithm written in C++ and licensed under the MIT License. This source is using Tarjan's implementation for the dense graph.