Zaawansowane algorytmy i struktury danych/Wykład 7

From Studia Informatyczne

Spis treści

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. image:End_of_proof.gif


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


\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. image:End_of_proof.gif


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.



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' = (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}. image:End_of_proof.gif

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'| \ge |\pi_1| +1. Kolejne fazy tego dowodu zobrazowane są na animacji poniżej.

Musimy jednak pamiętać, że ścieżka \pi' może przecinać więcej niż jedną ścieżkę z P. Załóżmy, że ścieżka \pi' przecina niektóre ścieżki z P w następującej kolejności: \pi_1, \pi_2, \ldots, \pi_t. Zauważmy, że z tych ścieżek i ścieżki \pi' możemy skonstruować zbiór t+1 nowych ścieżek. Ścieżkę R_1 konstruujemy biorąc początek ścieżki \pi', a następnie kawałek ścieżki \pi_1. Ścieżkę R_i, dla i=2,\ldots,t, konstruujemy biorąc kawałek ścieżki \pi_i, następnie kawałek ścieżki \pi', 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'. Sumaryczna długość ścieżek R_i jest o co najmniej 1 mniejsza niż sumaryczna długość ścieżek \pi_i' i ścieżki \pi'. Możemy więc zapisać:
1+ \sum_{i=1}^{t+1}|R_i| \le |\pi'| + \sum_{i=1}^{t}|\pi_i| = |\pi'| + 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'|,
co kończy dowód lematu. image:End_of_proof.gif

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}_Mskonstruowanego 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. image:End_of_proof.gif

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. image:End_of_proof.gif

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


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|). image:End_of_proof.gif