Zaawansowane algorytmy i struktury danych/Wykład 7

Abstrakt

W wykładzie tym skoncentrujemy się na problemie znajdowania najliczniejszych skojarzeń w grafach dwudzielnych. Zaczniemy od przedstawienia idei ścieżek powiększających, a następie użyjemy jej do konstrukcji algorytmu znajdującego maksymalne skojarzenie w grafie $G=(V,E)$ w czasie $O(|V||E|)$. Następnie przedstawimy algorytm Hopcrofta-Karpa, który działać będzie w czasie $O(\sqrt{|V|}|E|)$.

Problem maksymalnego skojarzenia w grafie dwudzielnym

Niech $G=(V,E)$ będzie grafem nieskierowanym. Skojarzeniem w grafie $G$ nazywamy każdy podzbiór krawędzi $M\subseteq E$ taki, w którym co najwyżej jedna krawędź z $M$ jest incydentna z każdym wierzchołkiem w $V$. O wierzchołku $v$ incydentnym do pewniej krawędzi z $M$ mówimy, że jest skojarzony, w przeciwnym przypadku $v$ nazywamy wolnym. Podobnie jeżeli krawędź $e$ należy do skojarzenia, mówimy, że jest ona skojarzona a w przeciwnym wypadku mówimy, że jest to krawędź wolna. Skojarzenie $M$ nazywamy maksymalnym gdy ma ono największą liczność spośród skojarzeń w $G$. W trakcie tego wykładu zajmiemy się tylko problemem znajdowania skojarzeń w grafach dwudzielnych, czyli takich, w których zbiór wierzchołków można podzielić na $V=V_1\cup V_2$, gdzie $V_1$ i $V_2$ są rozłączne, a wszystkie krawędzie z $E$ prowadzą pomiędzy $V_1$ i $V_2$.

Ścieżki powiększające

Ścieżką powiększającą nazwiemy ścieżkę prostą $p$ taką, że jej krawędzie są na przemian skojarzone i wolne, a końce są wolne. Łatwo zauważyć, że jeżeli istnieje ścieżka powiększająca $p$ względem $M$, to $M$ nie jest skojarzeniem maksymalnym. Używając wtedy ścieżki $p$, możemy skonstruować skojarzenie większe biorąc $M=M\oplus p$, czyli zamieniając na ścieżce krawędzie wolne na skojarzone i na odwrót. Możemy pokazać także przeciwne wynikanie:

Twierdzenie 1 [Twierdzenie Berge'a o ścieżkach powiększających]

Skojarzenie $M$ jest maksymalne, gdy nie istnieje względem niego żadna ścieżka powiększająca.

Dowód

Załóżmy przeciwnie, że istnieje skojarzenie $M^{\prime }$ liczniejsze niż $M$. Rozważmy graf $G^{\prime }=(V,M\oplus M^{\prime })$. Zauważmy, że w $G^{\prime }$ każdy wierzchołek ma stopień co najwyżej $2$, w związku z tym $G^{\prime }$ składa się z rozłącznych ścieżek i cykli. Na każdym cyklu występuje tyle samo krawędzi z $M$ co $M^{\prime }$. Natomiast w ścieżkach może występować co najwyżej o jedną krawędź więcej z któregoś skojarzenia. W grafie $G^{\prime }$ jest więcej krawędzi z $M^{\prime }$ niż z $M$, a zatem musi też istnieć ścieżka, na której jest więcej krawędzi z $M^{\prime }$. Musi to być oczywiście ścieżka powiększająca.

Algorytm wykorzystujący ścieżki powiększające

Zastanówmy się teraz, jak efektywnie sprawdzić, czy w grafie dwudzielnym nie ma ścieżki powiększającej, bądź jeżeli jest, to jak ją znaleźć. Dla grafu dwudzielnego $G=(V_1\cup V_2,E)$ oraz skojarzenia $M$ zdefiniujmy skierowany graf $G_M=(V_1\cup V_2,E_M)$ jako

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} {E}_M &=& \{(v_1, v_2): v_1v_2 \in E, v_1 \in V_1, v_2 \in V_2\}\\ &\cup& \{(v_2, v_1): v_1v_2 \in M, v_1 \in V_1, v_2 \in V_2\} \end{array} }

Algorytm znajdowania ścieżki powiększającej

---

 ZNAJDŹ-ŚCIEŻKĘ-POWIĘKSZAJĄCĄ$(G=(V_1\cup V_2,E),M)$
 1  ${V_1}^{\prime }=$ zbiór wierzchołków wolnych w $V_1$
 2  ${V_2}^{\prime }=$ zbiór wierzchołków wolnych w $V_2$
 3  skonstruuj graf skierowany $G_M=(V_1\cup V_2,E_M)$
 5  znajdź ścieżkę $p$ z ${V_1}^{\prime }$ do ${V_2}^{\prime }$ w $G_M$
 6  if $p$ nie istnieje then
 7    return $NIL$ (nie ma ścieżki powiększającej)
 8  usuń cykle z $p$ tak aby $p$ była ścieżką prostą
 9  return $p$ ($p$ to ścieżka powiększająca w $G$)

Lemat 2

Powyższy algorytm znajduje ścieżkę $p$ wtedy i tylko wtedy, gdy w $G$ istnieje ścieżka powiększająca względem $M$. Co więcej, znaleziona ścieżka jest ścieżką powiększającą.

Dowód

Załóżmy, że ścieżka $p$ istnieje. Z konstrukcji algorytmu wiemy, że jest to ścieżka, która

1. zaczyna się w wierzchołku wolnym,
2. z $V_1$ do $V_2$ idzie krawędzią wolną,
3. z $V_2$ do $V_1$ wraca krawędzią skojarzoną,
4. kończy się w $V_2$ krawędzią wolną.

Ścieżka $p$ spełnia wszystkie warunki dla ścieżki powiększającej oprócz bycia ścieżką prostą. Jeżeli $p$ przechodzi dwa razy przez ten sam wierzchołek $v\in V_1$, to wchodzi do niego dwa razy krawędzią skojarzoną, a wychodzi krawędzią nieskojarzoną. Jeżeli teraz usuniemy kawałek ścieżki pomiędzy tymi dwoma wejściami do $v$ (linia 8) to powyższe cztery warunki nadal będą zachodzić. Możemy więc, zachowując je, zamienić ścieżkę $p$ na ścieżkę prostą.

Natomiast jeżeli w grafie $G$ jest ścieżka powiększająca względem $M$, to możemy ją wprost przetłumaczyć na ścieżkę w gafie $G_M$.

Jesteśmy już gotowi, aby skonstruować pierwszy algorytm znajdujący maksymalne skojarzenie w grafie dwudzielnym.

Algorytm znajdujący maksymalne skojarzenie w grafie dwudzielnym

---

 MAKSYMALNE-SKOJARZENIE(G = (V_1 \cup V_2,E))
 1  $M=\mathrm{\varnothing }$
 1  repeat
 2    $p=$ZNAJDŹ-ŚCIEŻKĘ-POWIĘKSZAJĄCĄ$(G,M)$
 3    if $p\ne NIL$ then
 4      $M=M\oplus p$
 6  until $p=NIL$
 5  return $M$

Wyszukiwanie ścieżki powiększającej zobrazowane jest na poniższej animacji.

Plik:Zasd ilustr d.svg

Poprawność tego algorytmu wynika z Lematu 2 oraz Twierdzenia Berge'a. Ponieważ $\frac{|V|}{2}$ jest ograniczeniem górnym na rozmiar maksymalnego skojarzenia, a w każdym kroku pętli rozmiar skojarzenia rośnie o $1$, to pętla ta zostanie wykonana co najwyżej $O(|V|)$ razy. Wyszukanie jednej ścieżki powiększającej zajmuje czas $O(|E|)$, a więc całkowity czas działania algorytmu to $O(|V||E|)$.

Algorytm Hopcrofta-Karpa

Algorytm Hopcrofta-Karpa także wykorzystuje technikę ścieżek powiększających. Jednak w celu przyśpieszenia działania tej metody, zamiast wyszukiwać ścieżki pojedynczo, będziemy szukać wielu ścieżek na raz. Będziemy to robić jednak w taki sposób, aby długości tych ścieżek systematycznie rosły, będziemy mogli skorzystać wtedy z następującego lematu, który mówi, że długich ścieżek jest mało.

Lemat 3

Niech $M^{*}$ będzie skojarzeniem maksymalnym, a $M$ pewnym dowolnym skojarzeniem w $G$. Jeżeli długość najkrótszej ścieżki powiększającej względem $M$ wynosi $k$, to $|M^{*}|-|M|\le \frac{|V|}{k}$.

Dowód

Podobnie jak w dowodzie Twierdzenia Berge'a rozważmy graf $G^{\prime }=(V,M\oplus M^{\prime })$. Graf ten zawiera co najwyżej $|M^{*}|-|M|$ ścieżek powiększających względem $M$, długość każdej z tych ścieżek musi być co najmniej $k$. Sumaryczna długość tych ścieżek nie przekracza $|V|$, a więc nie może ich być więcej niż $\frac{|V|}{k}$.

Maksymalny zbiór rozłącznych wierzchołkowy ścieżek powiększających

W celu zagwarantowania wzrostu długości ścieżek po każdej fazie będziemy w każdej fazie konstruuować maksymalny zbiór rozłącznych wierzchołkowo najkrótszych ścieżek powiększających $P$. Pokażemy teraz, że po powiększeniu skojarzenia przy pomocy wszystkich tych ścieżek długość najkrótszej ścieżki rośnie. Oznaczmy przez $M\oplus P=M\oplus \underset{p\in P}{⨁}p$.

Lemat 4

Niech $P$ będzie maksymalnym rozłącznym wierzchołkowo zbiorem najkrótszych ścieżek powiększających względem $M$, wtedy długość najkrótszej ścieżki powiększającej względem $M\oplus P$ jest większa niż długość najkrótszej ścieżki powiększającej względem $M$.

Dowód

Weźmy najkrótszą ścieżkę powiększająca ${\pi }^{\prime }$ względem $M\oplus P$. Ścieżka ta musi przecinać się z pewną ścieżką ${\pi }_1$ ze zbioru $P$, inaczej musielibyśmy powiększyć $P$ o ${\pi }_1$. Pokażemy teraz, że $|{\pi }^{\prime }|\ge |{\pi }_1|+1$. Kolejne fazy tego dowodu zobrazowane są na animacji poniżej.

Plik:Zasd ilustr o.svg

Musimy jednak pamiętać, że ścieżka ${\pi }^{\prime }$ może przecinać więcej niż jedną ścieżkę z $P$. Załóżmy, że ścieżka ${\pi }^{\prime }$ przecina niektóre ścieżki z $P$ w następującej kolejności: ${\pi }_1,{\pi }_2,\dots ,{\pi }_t$. Zauważmy, że z tych ścieżek i ścieżki ${\pi }^{\prime }$ możemy skonstruować zbiór $t+1$ nowych ścieżek. Ścieżkę $R_1$ konstruujemy biorąc początek ścieżki ${\pi }^{\prime }$, a następnie kawałek ścieżki ${\pi }_1$. Ścieżkę $R_i$, dla $i=2,\dots ,t$, konstruujemy biorąc kawałek ścieżki ${\pi }_i$, następnie kawałek ścieżki ${\pi }^{\prime }$, a potem kawałek ścieżki ${\pi }_{i+1}$. Ostatnią ze ścieżek $R_{t+1}$ konstruujemy biorąc kawałek ścieżki ${\pi }_t$ i koniec ścieżki ${\pi }^{\prime }$. Sumaryczna długość ścieżek $R_i$ jest o co najmniej $1$ mniejsza niż sumaryczna długość ścieżek ${{\pi }_i}^{\prime }$ i ścieżki ${\pi }^{\prime }$. Możemy więc zapisać:

$1+\sum _{i=1}^{t+1}|R_i|\le |{\pi }^{\prime }|+\sum _{i=1}^t|{\pi }_i|=|{\pi }^{\prime }|+t|{\pi }_1|.$

Zauważmy, że ścieżki $R_i$ są ścieżkami powiększającymi względem $M$. Ich długości muszą być co najmniej takie, jak długość ścieżek ${\pi }_i$ i:

$1\le -|{\pi }_1|+|{\pi }^{\prime }|$,

co kończy dowód lematu.

Zajmijmy się teraz algorytmem konstrukcji zbioru ścieżek $P$. W konstrukcji tej użyjemy trochę zmodyfikowanej procedury DFS.

Algorytm częściowego DFS

---

 CZĘŚCIOWE-DFS$(G,v,T)$
 1  uruchom DFS(G,v) aż do momentu znalezienia pierwszego wierzchołka ze zbioru $T$
 2  usuń wszystkie odwiedzone wierzchołki w procedurze DFS z grafu $G$
 2  if istnieje ścieżka $p$ z $v$ do $T$ then
 4    return p
 5  else
 6    return NIL

Procedura ta różni się od standardowej procedury DFS w dwóch aspektach. Po pierwsze, prowadzi wyszukiwanie tylko do momentu znalezienia wierzchołka ze zbioru $T$. Po drugie, po zakończonym wyszukiwaniu usuwa wszystkie odwiedzone wierzchołki, tak aby każda następna znaleziona ścieżka przez nie nie przechodziła. Procedurę tę zastosujemy do grafu warstwowego ${\bar{G}}_M$skonstruowanego z grafu $G_M$. Niech ${V_1}^{\prime }$ oznacza zbiór wierzchołków wolnych w $V_1$. Oznaczmy przez $d:V\to {𝒩}$ odległość $d(v)$ wierzchołka $v$ od wierzchołków z ${V_1}^{\prime }$. Graf ${\bar{G}}_M=(V_1\cup V_2,{\bar{E}}_M)$ ma następujący zbiór krawędzi:

${\bar{E}}_M=\{(u,v):(u,v)\in E_M\text{ i }d(u)+1=d(v)\}.$

Lemat 5

Każda ścieżka w grafie ${\bar{G}}_M$, zaczynająca się w ${V_1}^{\prime }$, jest najkrótszą ścieżką w grafie $G_M$.

Dowód

Lemat ten wynika wprost z definicji najkrótszej ścieżki, tzn. ścieżka jest najkrótsza, jeżeli jej długość jest równa odległości z jej początku do jej końca.

Lemat ten pozwala nam na konstrukcję następującego algorytmu, wyszukującego maksymalny zbiór wierzchołkowo rozłącznych najkrótszych ścieżek powiększających.

Algorytm znajdujący maksymalny zbiór wierzchołkowo rozłącznych najkrótszych ścieżek powiększających

---

 MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK$(G=(V_1\cup V_2,E),M)$
 1  $P=\mathrm{\varnothing }$
 2  skonstruuj graf ${\bar{G}}_M=(V_1\cup V_2,{\bar{E}}_M)$
 3  niech ${V_1}^{\prime }$ będzie zbiorem wierzchołków wolnych w $V_1$
 4  for $v\in {V_1}^{\prime }$ do
 5  begin
 6    $p=$CZĘŚCIOWE-DFS$(G,v,T)$
 7    if $p\ne NIL$ then
 8      $P=P\cup p$ 
 9  end
 10 return $P$

Lemat 6

Algorytm MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK znajduje maksymalny zbiór wierzchołkowo rozłącznych najkrótszych ścieżek powiększających względem $M$ w czasie $O(|E|)$.

Dowód

Zauważmy, że czas działania $O(|E|)$ algorytmu wynika z konstrukcji CZĘŚCIOWE-DFS, która rozpatruje każdy wierzchołek tylko raz, a zatem także każda krawędź rozpatrywana jest tylko raz. Co więcej, usuwanie przejrzanych wierzchołków gwarantuje, że $P$ zawiera ścieżki wierzchołkowo rozłączne. To, że są to ścieżki najkrótsze wynika natomiast z Lematu 5.

Algorytm

Zapiszmy teraz algorytm Hopcrofta-Karpa.

Algorytm Hopcrofta-Karpa

---

 HOPCROFT-KARP$(G=(V_1\cup V_2,E))$
 1  $M=\mathrm{\varnothing }$
 2  repeat
 3    $P=$MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK$(G=(V_1\cup V_2,E),M)$
 4    if $P\ne NIL$ then
 5      $M=M\oplus P$
 6  until $P=NIL$
 7  return $M$

Plik:Zasd ilustr h.svg

Twierdzenie 7

Algorytm Hopcrofta-Karpa znajduje maksymalne skojarzenie w grafie dwudzielnym w czasie $O(\sqrt{|V|}|E|)$.

Dowód

Poprawność algorytmu wynika z Twierdzenia Berge'a ponieważ, jeżeli graf zawiera ścieżkę powiększającą, to zbiór $P$ nie będzie pusty. Lemat 4 mówi, że po każdym wykonaniu głównej pętli algorytmu długość najkrótszej ścieżki powiększającej jest większa o co najmniej 1. Dlatego po $\sqrt{|V|}$ krokach wynosić będzie ona co najmniej $\sqrt{|V|}$. Z Lematu 3 wiemy, że w takim wypadku pozostało nam jeszcze nie więcej niż $\sqrt{|V|}$ ścieżek do znalezienia i zostanie jeszcze wykonanych co najwyżej $\sqrt{|V|}$ obrotów pętli. W sumie pętla wykonana będzie nie więcej niż $2\sqrt{|V|}$ razy. Każde wykonanie pętli zajmuje czas $O(|E|)$ (Lemat 6), a więc całkowity czas działania algorytmu wynosi $O(\sqrt{|V|}|E|)$.