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'$ liczniejsze niż $M$. Rozważmy graf $G'=(V,M\oplus M')$. Zauważmy, że w $G'$ każdy wierzchołek ma stopień co najwyżej $2$, w związku z tym $G'$ składa się z rozłącznych ścieżek i cykli. Na każdym cyklu występuje tyle samo krawędzi z $M$ co $M'$. Natomiast w ścieżkach może występować co najwyżej o jedną krawędź więcej z któregoś skojarzenia. W grafie $G'$ jest więcej krawędzi z $M'$ niż z $M$, a zatem musi też istnieć ścieżka, na której jest więcej krawędzi z $M'$. 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}'=$ zbiór wierzchołków wolnych w $V_{1}$
 2  $V_{2}'=$ 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}'$ do $V_{2}'$ 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=\emptyset$
 1  repeat
 2    $p=$ZNAJDŹ-ŚCIEŻKĘ-POWIĘKSZAJĄCĄ$(G,M)$
 3    if $p\neq 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.

<flash>file=Zasd_ilustr_d.swf |width=800|height=300</flash>

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|\leq {\frac {|V|}{k}}$.

Dowód

Podobnie jak w dowodzie Twierdzenia Berge'a rozważmy graf $G'=(V,M\oplus M')$. 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 \bigoplus _{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 '$ 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 '|\geq |\pi _{1}|+1$. Kolejne fazy tego dowodu zobrazowane są na animacji poniżej. <flash>file=Zasd_ilustr_o.swf

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 ${\overline {G}}_{M}$skonstruowanego z grafu ${G}_{M}$. Niech $V_{1}'$ oznacza zbiór wierzchołków wolnych w $V_{1}$. Oznaczmy przez $d:V\to {\mathcal {N}}$ odległość $d(v)$ wierzchołka $v$ od wierzchołków z $V_{1}'$. Graf ${\overline {G}}_{M}=(V_{1}\cup V_{2},{\overline {E}}_{M})$ ma następujący zbiór krawędzi:

${\overline {E}}_{M}=\{(u,v):(u,v)\in E_{M}{\mbox{ i }}d(u)+1=d(v)\}.$

Lemat 5

Każda ścieżka w grafie ${\overline {G}}_{M}$, zaczynająca się w $V_{1}'$, 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=\emptyset$
 2  skonstruuj graf ${\overline {G}}_{M}=(V_{1}\cup V_{2},{\overline {E}}_{M})$
 3  niech $V_{1}'$ będzie zbiorem wierzchołków wolnych w $V_{1}$
 4  for $v\in V_{1}'$ do
 5  begin
 6    $p=$CZĘŚCIOWE-DFS$(G,v,T)$
 7    if $p\neq 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=\emptyset$
 2  repeat
 3    $P=$MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK$(G=(V_{1}\cup V_{2},E),M)$
 4    if $P\neq NIL$ then
 5      $M=M\oplus P$
 6  until $P=NIL$
 7  return $M$

<flash>file=Zasd_ilustr_h.swf |width=800|height=300</flash>

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|)$.