Zaawansowane algorytmy i struktury danych/Wykład 7

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 w czasie . Następnie przedstawimy algorytm Hopcrofta-Karpa, który działać będzie w czasie .

Problem maksymalnego skojarzenia w grafie dwudzielnym

Niech będzie grafem nieskierowanym. Skojarzeniem w grafie nazywamy każdy podzbiór krawędzi taki, w którym co najwyżej jedna krawędź z jest incydentna z każdym wierzchołkiem w . O wierzchołku incydentnym do pewniej krawędzi z mówimy, że jest skojarzony, w przeciwnym przypadku nazywamy wolnym. Podobnie jeżeli krawędź należy do skojarzenia, mówimy, że jest ona skojarzona a w przeciwnym wypadku mówimy, że jest to krawędź wolna. Skojarzenie nazywamy maksymalnym gdy ma ono największą liczność spośród skojarzeń w . 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 , gdzie i są rozłączne, a wszystkie krawędzie z prowadzą pomiędzy i .

Ścieżki powiększające

Ścieżką powiększającą nazwiemy ścieżkę prostą 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 względem , to nie jest skojarzeniem maksymalnym. Używając wtedy ścieżki , możemy skonstruować skojarzenie większe biorąc , 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 jest maksymalne, gdy nie istnieje względem niego żadna ścieżka powiększająca.

Dowód

Załóżmy przeciwnie, że istnieje skojarzenie liczniejsze niż . Rozważmy graf . Zauważmy, że w każdy wierzchołek ma stopień co najwyżej , w związku z tym składa się z rozłącznych ścieżek i cykli. Na każdym cyklu występuje tyle samo krawędzi z co . Natomiast w ścieżkach może występować co najwyżej o jedną krawędź więcej z któregoś skojarzenia. W grafie jest więcej krawędzi z niż z , a zatem musi też istnieć ścieżka, na której jest więcej krawędzi z . Musi to być oczywiście ścieżka powiększająca. 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 oraz skojarzenia zdefiniujmy skierowany graf 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Ą
 1   zbiór wierzchołków wolnych w 
 2   zbiór wierzchołków wolnych w 
 3  skonstruuj graf skierowany 
 5  znajdź ścieżkę  z  do  w 
 6  if  nie istnieje then
 7    return  (nie ma ścieżki powiększającej)
 8  usuń cykle z  tak aby  była ścieżką prostą
 9  return  ( to ścieżka powiększająca w )

Lemat 2

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

Dowód

Załóżmy, że ścieżka istnieje. Z konstrukcji algorytmu wiemy, że jest to ścieżka, która
  1. zaczyna się w wierzchołku wolnym,
  2. z do idzie krawędzią wolną,
  3. z do wraca krawędzią skojarzoną,
  4. kończy się w krawędzią wolną.

Ścieżka spełnia wszystkie warunki dla ścieżki powiększającej oprócz bycia ścieżką prostą. Jeżeli przechodzi dwa razy przez ten sam wierzchołek , 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 (linia 8) to powyższe cztery warunki nadal będą zachodzić. Możemy więc, zachowując je, zamienić ścieżkę na ścieżkę prostą.

Natomiast jeżeli w grafie jest ścieżka powiększająca względem , to możemy ją wprost przetłumaczyć na ścieżkę w gafie . 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  
 1  repeat
 2    ZNAJDŹ-ŚCIEŻKĘ-POWIĘKSZAJĄCĄ
 3    if  then
 4      
 6  until 
 5  return 

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

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

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 będzie skojarzeniem maksymalnym, a pewnym dowolnym skojarzeniem w . Jeżeli długość najkrótszej ścieżki powiększającej względem wynosi , to .

Dowód

Podobnie jak w dowodzie Twierdzenia Berge'a rozważmy graf . Graf ten zawiera co najwyżej ścieżek powiększających względem , długość każdej z tych ścieżek musi być co najmniej . Sumaryczna długość tych ścieżek nie przekracza , a więc nie może ich być więcej niż . 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 . Pokażemy teraz, że po powiększeniu skojarzenia przy pomocy wszystkich tych ścieżek długość najkrótszej ścieżki rośnie. Oznaczmy przez .

Lemat 4

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

Dowód

Weźmy najkrótszą ścieżkę powiększająca względem . Ścieżka ta musi przecinać się z pewną ścieżką ze zbioru , inaczej musielibyśmy powiększyć o . Pokażemy teraz, że . Kolejne fazy tego dowodu zobrazowane są na animacji poniżej.

Musimy jednak pamiętać, że ścieżka może przecinać więcej niż jedną ścieżkę z . Załóżmy, że ścieżka przecina niektóre ścieżki z w następującej kolejności: . Zauważmy, że z tych ścieżek i ścieżki możemy skonstruować zbiór nowych ścieżek. Ścieżkę konstruujemy biorąc początek ścieżki , a następnie kawałek ścieżki . Ścieżkę , dla , konstruujemy biorąc kawałek ścieżki , następnie kawałek ścieżki , a potem kawałek ścieżki . Ostatnią ze ścieżek konstruujemy biorąc kawałek ścieżki i koniec ścieżki . Sumaryczna długość ścieżek jest o co najmniej mniejsza niż sumaryczna długość ścieżek i ścieżki . Możemy więc zapisać:


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


co kończy dowód lematu. End of proof.gif

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

Algorytm częściowego DFS


 CZĘŚCIOWE-DFS
 1  uruchom DFS(G,v) aż do momentu znalezienia pierwszego wierzchołka ze zbioru 
 2  usuń wszystkie odwiedzone wierzchołki w procedurze DFS z grafu 
 2  if istnieje ścieżka  z  do  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 . 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 skonstruowanego z grafu . Niech oznacza zbiór wierzchołków wolnych w . Oznaczmy przez odległość wierzchołka od wierzchołków z . Graf ma następujący zbiór krawędzi:


Lemat 5

Każda ścieżka w grafie , zaczynająca się w , jest najkrótszą ścieżką w grafie .

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. 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
 1  
 2  skonstruuj graf 
 3  niech  będzie zbiorem wierzchołków wolnych w 
 4  for  do
 5  begin
 6    CZĘŚCIOWE-DFS
 7    if  then
 8       
 9  end
 10 return 

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 w czasie .

Dowód

Zauważmy, że czas działania 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 zawiera ścieżki wierzchołkowo rozłączne. To, że są to ścieżki najkrótsze wynika natomiast z Lematu 5. End of proof.gif

Algorytm

Zapiszmy teraz algorytm Hopcrofta-Karpa.

Algorytm Hopcrofta-Karpa


 HOPCROFT-KARP
 1  
 2  repeat
 3    MAKSYMALNY-ZBIÓR-NAJKRÓTSZYCH-ŚCIEŻEK
 4    if  then
 5      
 6  until 
 7  return 

Twierdzenie 7

Algorytm Hopcrofta-Karpa znajduje maksymalne skojarzenie w grafie dwudzielnym w czasie .

Dowód

Poprawność algorytmu wynika z Twierdzenia Berge'a ponieważ, jeżeli graf zawiera ścieżkę powiększającą, to zbiór 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 krokach wynosić będzie ona co najmniej . Z Lematu 3 wiemy, że w takim wypadku pozostało nam jeszcze nie więcej niż ścieżek do znalezienia i zostanie jeszcze wykonanych co najwyżej obrotów pętli. W sumie pętla wykonana będzie nie więcej niż razy. Każde wykonanie pętli zajmuje czas (Lemat 6), a więc całkowity czas działania algorytmu wynosi . End of proof.gif