Edmondsov algoritam

Ovaj članak je o algoritmu optimalnog grananja. Za algoritam maksimalnog poklapanja pogledajte Algoritam maksimalnog uparivanja.

U teoriji grafova, grani matematike, Edmondsov algoritam ili Ču-Liu/Edmondsov algoritam je algoritam za pronalaženje maksimalnog ili minimalnog optimalnog grananja. Ovaj algoritam je sličan problemu minimalnog razapinjućeg stabla, koji se tiče neusmerenih grafova. Ipak, kada su čvorovi povezani usmerenim granama sa težinskim koeficijentima, algoritam minimalnog razapinjućeg stabla se ne može koristiti.

Algoritam optimalnog grananja su predložili nezavisno Jeng-jin Ču (Yoeng-jin Chu) i Ceng-hong Liu (Tseng-hong Liu) 1965. godine, a zatim i Edmonds 1967. godine. Za pronalazak putanje maksimalne dužine, uzima se grana sa najvećim težinskim koeficijentom i povezuju se odgovarajuća dva čvora, zatim se uzima sledeća grana po težini, itd. Ako odabrana grana pravi petlju, uklanja se i bira se naredna grana. Pronalazak putanje minimalne dužine se vrši analogno, odabirom grane sa najmanjom težinom.

Složenost algoritma

Složenost ovog algoritma je reda $O(EV)$. Postoji i brža implementacija, koju je predložio Robert Tarjan. Složenost tog algoritma je reda $O(E\log V)$ za retki graf, a reda $O(V^{2})$ za zbijeni graf. Taj algoritam je brz koliko i Primov algoritam za minimalno povezujuće stablo. 1986. godine , Gabov (Gabow), Galil (Galil), Spenser (Spencer), i Tarjan (Tarjan) su napravili bržu implementaciju, reda $O(E+V\log V)$.

Algoritam

Opis

Algoritam je rekurzivan. Sa $f$ je označena funkcija koja za dati usmereni graf sa težinskim koeficijentima $D$ i čvorom $r$ koji predstavlja koren, vraća povezujuće stablo minimalne težine, sa korenom u $r$.

Za dati usmereni graf $D$ sa težinskim koeficijentima i koren $r$ zamenimo bilo koji skup paralelnih grana (grana između dva ista čvora, u istom pravcu) jednom granom sa težinom jednakom najmanjoj težini u datom skupu grana.

Dalje, za svaki čvor $v$ različit od $r$, obeležimo dolazeću granu najmanje težine. Označimo drugi kraj te grane sa $\pi (v)$. Grana je tako označena sa $(\pi (v),v)$, a pridružena težina sa $w(\pi (v),v)$. Ako obeležene grane formiraju stablo najkraće putanje, $f(D)$ je to stablo. U suprotnom, skup obeleženih grana formira bar jednu petlju. Neka je $C$ jedna od ovih petlji (nasumično odabrana). Definišemo usmereni graf sa težinskim koeficijentima, $D^{\prime }$ i korenom u $r^{\prime }$ prema sledećem uputstvu: čvorovi $D^{\prime }$ su čvorovi $D$ koji se ne nalaze u $C$ i novi čvor je označen sa $v_{C}$.

Ako je $(u,v)$ grana u $D$ gde je $u\notin C$ i $v\in C$, onda treba uključiti u $D^{\prime }$ granu $e=(u,v_{C})$, i definisati $w(e)=w(u,v)-w(\pi (v),v)$.

Ako je $(u,v)$ grana u $D$ gde je $u\in C$ i $v\notin C$, onda treba uključiti u $D^{\prime }$ granu $e=(v_{C},v)$, i definisati $w(e)=w(u,v)$.

Ako je $(u,v)$ grana u $D$ gde je $u\notin C$ i $v\notin C$, onda treba uključiti u $D^{\prime }$ granu $e=(u,v)$, i definisati $w(e)=w(u,v)$.

U $D^{\prime }$ se ne uključuje nijedna druga grana.

Koren $r^{\prime }$ stabla $D^{\prime }$ je koren $r$ stabla $D$.

Pozivom funkcije $f(D^{\prime })$, nalazi se stablo najkraće putanje za $D^{\prime }$. Prvo, označe se u stablu $D$ sve grane koje su i u $D^{\prime }$, a koje su označene u stablu najkraće putanje(SNP) za $D^{\prime }$. Takođe, označe se u $D$ sve grane iz $C$. Dalje, pretpostavimo da je u SNP za $D^{\prime }$, (jedinstvena) dolazeća grana u $v_{C}$ $(u,v_{C})$. Ta grana dolazi iz nekog para $(u,v)$ gde je $u\notin C$ i $v\in C$. Treba obrisati $(\pi (v),v)$ i označiti $(u,v)$. Takođe, za svaku označenu $(v_{C},v)$ u SNP za $D^{\prime }$ koja potiče od grane $(u,v)$ u $D$ gde je $u\in C$ i $v\notin C$, označiti granu $(u,v)$. Sada skup označenih grana formira SNP, što je povratna vrednost $f(D)$.

Implementacija

Neka je BV skup čvorova i BE skup grana. Neka je v čvor, a e grana sa najvećom pozitivnom težinom koja povezuje v. C_i je petlja. G₀ = (V₀,E₀) je originalni dijagram. u_i je zamenski čvor za 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)$

Spoljašnje veze

• 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.