Zaawansowane algorytmy i struktury danych/Wykład 8

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Abstrakt

W wykładzie tym skupimy się na problemie znajdowania maksymalnych skojarzeń w dowolnych grafach. Zaczniemy od postawienia twierdzenia Berge'a i udowodnienia jego części. Następnie przedstawimy i udowodnimy lemat o ściąganiu cykli. Wykorzystamy ten lemat w konstrukcji algorytmu Edmondsa, znajdującego maksymalne skojarzenia w czasie . Algorytm ten będzie jednocześnie konstruktywnym dowodem twierdzenia Berga.

Skojarzenie w grafach dowolnych

Na poprzednim wykładzie, aby pokazać poprawność algorytmu znajdowania doskonałych skojarzeń, skorzystaliśmy z twierdzenia Berge'a o ścieżkach powiększających, które mówiło, że skojarzenie jest maksymalne, gdy nie istnieje względem niego ścieżka powiększająca. Tutaj skorzystamy z komplementarnego podejścia, a mianowicie wykorzystamy poniższy lemat. Jednak do jego sformułowania musimy wprowadzić jedno oznaczenie. Niech oznacza liczbę spójnych składowych grafu o nieparzystej liczbie wierzchołków.

Lemat 1

Dla dowolnego skojarzenia w grafie i dowolnego podzbioru wierzchołków zachodzi

     (1)

Dowód

Zauważmy, że jeżeli nieparzystej składowej z grafu nie skojarzymy z wierzchołkiem z , to pozostanie w niej co najmniej jeden wierzchołek wolny. Ponieważ z nieparzystych składowych możemy skojarzyć w ten sposób co najwyżej , to dla dowolnego skojarzenia w grafie pozostanie co najmniej wierzchołków wolnych. Tak więc skojarzonych wierzchołków będzie co najwyżej , a co za tym idzie, rozmiar jest ograniczony tak jak we wzorze 1. End of proof.gif

Lemat ten mówi, że aby udowodnienić, że skojarzenie jest maksymalne, musimy pokazać zbiór , dla którego we wzorze 1 będzie zachodziła równość. Niestety, lemat ten nie mówi, że taki zbiór musi istnieć. Jednak algorytm Edmondsa, który za chwilę przedstawimy, pozwoli na konstrukcję takiego zbioru, a tym samym pozwoli nam na udowodnienie następującej silniejszej wersji Lematu 1.

Twierdzenie 2 [Twierdzenie Berge'a]

Niech będzie maksymalnym skojarzeniem w grafie , wtedy

     (2)

Lemat o ściąganiu cykli

Głównym problemem w konstrukcji algorytmu, znajdującego maksymalne skojarzenie w grafach dowolnych, jest problem znalezienia ścieżki powiększającej. Niestety, konstrukcja grafu użyta przez nas na poprzednim wykładzie tutaj nie zadziała, ponieważ teraz mogą istnieć naprzemienne ścieżki zaczynające się w wierzchołku wolnym i kończące się krawędzią skojarzoną i nie skojarzoną w wybranym wierzchołku. Nie możemy więc po prostu pamiętać, czy wierzchołek został juz odwiedzony i użyć dzięki temu prostego przeszukiwania grafu. Aby poradzić sobie z takimi trudnymi przypadkami, użyjemy następującego lematu.

Lemat 3 [O ściąganiu cykli]

Dla grafu niech:
  • będzie skojarzeniem w ,
  • będzie cyklem długości zawierającym krawędzi z i rozłącznym z resztą .
Skonstruujmy nowy graf z poprzez ściągnięcie do jednego wierzchołka. Skojarzenie jest maksymalne w wtedy i tylko wtedy, gdy skojarzenie jest maksymalne w .

Dowód

Udowodnijmy najpierw, że jeżeli jest skojarzeniem maksymalnym, to także jest maksymalne. Załóżmy przeciwnie, że nie jest maksymalnym skojarzeniem w G. Wtedy istnieje ścieżka powiększająca względem . Jeżeli jest rozłączna z , to także jest ścieżką powiększającą względem i nie jest maksymalne. Zatem przecina się z . Ponieważ ma jeden wierzchołek wolny, to co najmniej jeden z końców nie leży na . Oznaczmy ten wierzchołek przez . Poczynając od , niech będzie pierwszym punktem na ścieżce leżącym na . Wtedy jest ścieżką powiększającą względem w , ponieważ po ściągnięciu do jest wolny.

Pokażemy teraz, że w lemacie zachodzi także wynikanie w drugim kierunku. Niech nie będzie maksymalnym skojarzeniem w oraz niech będzie liczniejszym skojarzeniem w . Rozwińmy cykl , aby odtworzyć . Wtedy będzie skojarzeniem w , kojarzącym co najwyżej jeden wierzchołek z . Możemy wtedy powiększyć o krawędzi z , otrzymując skojarzenie o rozmiarze:

.
Tak więc nie jest maksymalnym skojarzeniem w , co kończy dowód lematu. End of proof.gif

Lemat ten zobrazowany jest na poniższej animacji.

Zauważmy, że jeżeli znajdziemy większe skojarzenie od w , to nie tylko wiemy, że nie jest maksymalnym skojarzeniem, ale także umiemy skonstruować to większe skojarzenie. Zanim wykorzystamy tę obserwację w konstrukcji algorytmu Edmondsa, wprowadźmy pewne oznaczenia.

Algorytm Edmondsa

Niech będzie pewnym skojarzeniem oraz niech S oznacza zbiór wierzchołków wolnych dla . Lasem -alternującym nazwiemy las taki, że:

  • korzeniem każdego drzewa w jest wierzchołek i drzewo to nie zawiera innych wierzchołków z ,
  • każdy wierzchołek należy do jednej składowej ,
  • każda krawędź w odległości nieparzystej od korzenia należy do .

Zauważmy, że każdy punkt w lesie w odległości parzystej od ma stopień . Takie punkty nazywać będziemy wewnętrznymi. Pozostałe punkty w nazywać będziemy zewnętrznymi. Dla przykładu, las składający się tylko z punktów jest -alternujący.

Algorytm Edmondsa


 EDMONDS
 1  
 2  las  to zbiór wierzchołków wolnych
 3  repeat
 4    if istnieje zewnętrzny wierzchołek  sąsiedni z wierzchołkiem  then
 5    begin
 6      znajdź wierzchołek  taki, że 
 7      
 8    end
 9    else if  to wierzchołki zewnętrzne połączone krawędzią then
 10   begin
 11     if  należą do różnych składowych  then
 12     begin
 13       niech  to ścieżka z  do korzenia jego składowej
 14       rozwiń wszystkie ściągnięte cykle w grafie 
 15       
 16       las  to zbiór wierzchołków wolnych
 17     end
 18     else
 19     begin
 20       niech  będzie cyklem utworzonym przez krawędź  oraz ścieżkę  w ,
 21       niech  będzie ścieżką w  łączącą  z korzeniem drzewa
 22       
 23       utwórz graf  poprzez ściągnięcie 
 24       
 25     end
 26   end
 27   else
 28   begin
 29     rozwiń wszystkie ściągnięte cykle w grafie 
 30     return 
 31   end
 32 until FALSE

Działanie tego algorytmu zobrazowane jest na poniższej animacji.

Twierdzenie 4

Algorytm Edmondsa znajduje maksymalne skojarzenie w grafie .

Dowód

Algorytm Edmondsa kończy działanie, gdy każdy wierzchołek zewnętrzny w ma jako sąsiadów wierzchołki wewnętrzne. Oznaczmy przez zbiór wierzchołków wewnętrznych w , a przez zbiór wierzchołków zewnętrznych. Mamy wtedy , ponieważ w każdym drzewie jest jeden wierzchołek zewnętrzny więcej i jest to wierzchołek wolny. Jeżeli usuniemy wierzchołki z , otrzymamy graf składający się z izolowanych wierzchołków zewnętrznych. Dlatego i
czyli nierówność w lemacie 1 zachodzi z równością. Skojarzenie jest więc maksymalne. Zauważmy, że z lematu o ściąganiu cykli wynika, że będzie ono też maksymalne po rozwinięciu wszystkich ściągniętych cykli. End of proof.gif

Szczegóły implementacji

Wprost zaimplementowany algorytm Edmondsa zgodnie z tym schematem działać będzie w czasie . Aby zagwarantować czas działania , musimy uzupełnić jeszcze kilka szczegółów implementacyjnych. Po pierwsze, nie będziemy usuwać wierzchołków należących do ściąganych cykli, tylko etykietować je jako nieaktywne. Natomiast aby reprezentować wierzchołki otrzymane ze ściągnięcia cykli, będziemy dodawać nowe wierzchołki je reprezentujące - zwane pseudowierzchołkami. Dzięki temu łatwiej będzie nam odtwarzać sieć przy rozwijaniu ściągniętych cykli. Krawędzie mające jeden koniec będący wierzchołkiem nieaktywnym nazywać będziemy także nieaktywnymi. Pozostałe krawędzie są aktywne. W trakcie działania algorytmu ignorujemy wierzchołki i krawędzie nieaktywne.

Trzymanie informacji o krawędziach nieaktywnych w grafie może zwiększyć długość list sąsiedztwa. Po ściągnięciu cyklu wszystkim sąsiadującym z nim wierzchołkom wydłużają się listy sąsiedztwa o . Jednak w trakcie działania algorytmu wykonanych będzie co najwyżej kontrakcji, więc listy te będą długości co najwyżej .

Pokażemy teraz, że między znalezieniem kolejnych ścieżek powiększających upłynie czas . Pomijając czas potrzebny na ściąganie i rozwijanie cykli, czas potrzebny na przetworzenie każdego wierzchołka wynosi . Każdy wierzchołek przetworzony będzie tylko raz, w momencie dodania go do lasu , dlatego całkowity czas to . Pokażemy teraz, że na ściągnięcie wszystkich cykli i ich późniejsze rozwinięcie potrzeba także czasu .

Zajmijmy się teraz ściąganiem cykli. Niech to cykl . Problemem jest tutaj stworzenie listy sąsiadów dla pseudowierzchołka reprezentującego po ściągnięciu. W tym celu:

  • przeglądamy wierzchołki należące do cyklu i zaznaczmy wierzchołki z ,
  • przeglądamy teraz wierzchołki grafu i tworzymy listę wierzchołków zaznaczonych - to jest właśnie ,
  • dodajemy jako sąsiada wierzchołków .

Zauważmy, że każdy wierzchołek tylko raz może należeć do ściąganego cyklu. Przejrzenie list i markowanie wierzchołków zajmie więc w sumie czas . Pozostałe czynności w zajmują zawsze czas , co w sumie daje czas .

Przejdźmy teraz do problemu rozwinięcia cykli. Samo rozwinięcie cykli może być zrealizowane w czasie poprzez przejrzenie wszystkich wierzchołków oraz krawędzi w grafie, w trakcie którego usuwamy wszystkie pseudowierzchołki i markujemy nieaktywne elementy grafu jako aktywne. Robiąc to, musimy jednak pamiętać także o rozwijaniu ścieżki . Najpierw, przechodząc tę ścieżkę markujemy wszystkie wierzchołki do niej należące i zapisujemy dla nich w zmiennej ich poprzedników na ścieżce oraz w zmiennej ich następników. Jeżeli teraz rozwijamy pseudowierzchołek , który leży na ścieżce, to:

  • markujemy najpierw wierzchołki należące do ściągniętego cyklu reprezentowanego przez pseudowierzchołek ,
  • przeszukujemy listę sąsiadów w celu znalezienia zamarkowanego wierzchołka .
  • przeszukujemy listę sąsiadów w celu znalezienia zamarkowanego wierzchołka .
  • przechodzimy ściągnięty cykl w kierunku zadanym przez parzystość ścieżki, od wierzchołka do wierzchołka .

W ten sposób dla każdego rozwijanego kielicha musimy wykonać dodatkowych operacji, co przy rozwijaniu kielichów daje złożoność .