Zaawansowane algorytmy i struktury danych/Wykład 8

Abstrakt

W wykładzie tym skupimy się na problemie znajdowania skojarzeń w dowolnych grafach. Zaczniemy od postawienia twierdzenia Berge'a i udowodnienia jego słabszej wersji. Następnie udowodnimy lemat o ściąganiu cykli. Wykorzystując ten lemat pokażemy algorytmu Edmondsa znajdujący doskonałe skojarzenia w czasie $O(n^3)$, gdzie $n$ to liczba wierzchołków w grafie. Algorytm ten będzie jednocześnie końcem dowodu twierdzenia Berga.

Skojarzenie w grafach dowolnych

Na poprzednim wykładzie aby pokazać poprawność algorytmu znajdowania doskonałych skojarzeń skorzystaliśmy z twierdzenie Berge'a, 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 przed jego sformułowaniem wprowadźmy kilka oznaczeń. Niech $c_n(G)$ oznacza liczbę spójnych składowych grafu $G$ o nieparzystej liczbie wierzchołków.

Lemat 1

Dla dowolnego skojarzenia $M$ w grafie $G=(V,E)$ i dowolnego podzbioru wierzchołków Parser nie mógł rozpoznać (nieznana funkcja „\subsereq”): {\displaystyle X \subsereq V} zachodzi.

$|M|\le \frac{1}{2}(|V|-(c_n(G-X)-|X|))$      (1)

Dowód

Zauważmy, że jeżeli nieparzystej składowej z grafu $G-X$ nie skojarzymy z wierzchołkiem z $X$, to pozostanie w niej co najmniej jeden wierzchołek wolny. Ponieważ z $c_n(G-X)$ nieparzystych składowych możemy skojarzyć w ten sposób co najwyżej $|X|$, to dla dowolnego skojarzenia $M$ w grafie pozostanie co najmniej $c_n(G-X)-|X|$ wierzchołków wolnych. Czyli skojarzonych wierzchołków będzie co najwyżej $|V|-(c_n(G-X)-|X|)$ a co za tym idzie rozmiar $M$ jest ograniczony tak jak we wzorze 1.

Lemat ten mówi, że w celu udowodnienia, że skojarzenie $M$ jest maksymalne musimy pokazać zbiór $X\subseteq V$ taki, że 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 chile przedstawimy, pozwoli na konstrukcje takiego zbioru, a tym samym pozwoli nam na udowodnienie następującej silniejszej wersji Lematu 1.

Twierdzenie 2 [Berge'a]

Niech $M$ będzie maksymalnym skojarzeniem w grafie $G=(V,E)$, wtedy

$|M|=\min \left\{\frac{1}{2}(|V|-(c_0(G-X)-|X|))\right|X\subseteq V(G)\}.$      (2)

Lemat o ściąganiu cykli

Głównym problemem w konstrukcji algorytmu znajdującego maksymalne skojarzenie w grafach dowolnych jest problem znalezienia ścieżek powiększających. Niestety konstrukcja grafu $G_M$ użyta przez nas na poprzednim wykładzie tutaj nie zadziała, ponieważ w grafie do wierzchołka może istnieć naprzemienna ścieżka kończąca się krawędzią skojarzoną i nie skojarzoną. Nie możemy więc po prostu pamiętać, czy wierzchołek został juz odwiedzony i użyć dzięki temu prostego przeszukiwania grafu. W celu poradzenia sobie z takimi trudnymi przypadkami użyjemy następującego lematu.

Lemat 3 [O ściąganiu cykli]

Dla grafu $G$ niech:

• $M$ będzie skojarzeniem w $G$,
• $Z$ będzie cyklem długości $2k+1$ zawierającym $k$ krawędzi z $M$ i rozłącznym z resztą $M$.

Skonstruujmy nowy graf $G^{\prime }$ z $G$ poprzez ściągnięcie $Z$ do jednego wierzchołka. Skojarzenie $M^{\prime }=M-E(Z)$ jest maksymalne w $G^{\prime }$ wtedy i tylko wtedy gdy skojarzenie $M$ jest maksymalne w $G$.

Dowód

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

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

$|N|=|N^{\prime }|+k>|M^{\prime }|+k=|M|$.

Czyli $M$ nie jest maksymalnym skojarzeniem w $G$, co kończy dowód lematu.

Lemat ten zobrazowany jest na poniższej animacji. <flash>file=Zasd_Ilustr_m.swf |width=600|height=500</flash>

Zauważmy, że jeżeli znajdziemy większe skojarzenie od $M^{\prime }$ w $G^{\prime }$, to nie tylko wiemy, że $M$ 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 $M$ będzie pewnym skojarzeniem oraz niech S oznacza zbiór wierzchołków wolnych dla $M$. Lasem $M$-alternującym nazwiemy las $L$ taki, że:

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

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

Algorytm Edmondsa

---

 EDMONDS(G = (V,E))
 1  $M=\mathrm{\varnothing }$
 2  las $L$ to zbiór wierzchołków wolnych
 3  repeat
 4    if istnieje zewnętrzny wierzchołek $x\in L$ sąsiedni z wierzchołkiem $y\notin L$ then
 5    begin
 6      znajdź wierzchołek $z$ taki, że $yz\in M$
 7      $L=L+xy+yz$
 8    end
 9    else if $x_1,x_2\in L$ to wierzchołki zewnętrzne połączone krawędzią then
 10   begin
 11     if $x_1,x_2$ należą do różnych składowych $L$ then
 12     begin
 13       niech $P_i$ to ścieżka z $x_i$ do korzenia jego składowej
 14       rozwiń wszystkie ściągnięte cykle w grafie $G$
 15       $M=M\oplus (P_1+P_2+x_1{x}_2)$
 16       las $L$ to zbiór wierzchołków wolnych
 17     end
 18     else
 19     begin
 20       niech $C$ będzie cyklem utworzonym przez krawędź $x_1{x}_2$ oraz ścieżkę $x-y$ w $L$,
 21       niech $P$ będzie ścieżką w $L$ łączącą $C$ z korzeniem drzewa
 22       $M=M\oplus P$
 23       utwórz graf $G^{\prime }$ poprzez ściągnięcie $C$
 24       $G=G^{\prime }$
 25     end
 26   end
 27   else
 28   begin
 29     rozwiń wszystkie ściągnięte cykle w grafie $G$
 30     return $M$
 31   end
 32 until FALSE

Działanie tego algorytmu zobrazowane jest na poniższej animacji. <flash>file=Zasd_ilustr_n.swf |width=600|height=500</flash>

Twierdzenie 4

Algorytm Edmondsa znajduje maksymalne skojarzenie $M$ w grafie $G$.

Dowód

Algorytm Edmondsa kończy działanie gdy każdy wierzchołek zewnętrzny w $L$ ma jako sąsiadów wierzchołki wewnętrzne. Oznaczmy przez $W$ zbiór wierzchołków wewnętrznych w $L$ a przez $Z$ zbiór wierzchołków zewnętrznych. Mamy wtedy $|Z|-|W|=|V|-2|M|$, ponieważ w każdym drzewie jest jeden wierzchołek zewnętrzny więcej i jest to wierzchołek wolny. Jeżeli usuniemy wierzchołki $W$ z $G$, to otrzymamy graf składający się z izolowanych wierzchołków zewnętrznych. Dlatego $c_n(G-W)=|Z|$ i

$\frac{1}{2}(|V|-(c_n(G-W)-|W|))=\frac{1}{2}(|V|-|Z|+|W|))=\frac{1}{2}(2|M|)=|M|,$

czyli nierówność w lemacie 1 zachodzi z równością. Skojarzenie $M$ 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.

Szczegóły implementacji

Wprost zaimplementowany algorytm Ddmondsa zgodnie z tym schematem działać będzie w czasie $O(n^{2}m)$. W celu zagwarantowania czasu działania $O(n^3)$ 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 kielicha wszystkie sąsiednie do niego wierzchołki wierzchołki mają listy sąsiedztwa dłuższe o 1. Jednak jest co najwyżej $n/2$ kontrakcji więc listy te są długości co najwyżej $\frac{3}{2}n$.

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

Zajmijmy się teraz ściąganiem cykli. Niech $i_1-i_2-\dots -i_k-i_1$ to cykl $C$. Problemem jest tutaj stworzenie listy sąsiadów $\mathrm{\Gamma }(b)=\mathrm{\Gamma }(i_1)\cup \mathrm{\Gamma }(i_2)\cup \dots \mathrm{\Gamma }(i_k)$, dla pseudowierzchołka $b$ reprezentującego $B$ po ściągnięciu. W tym celu:

• przeglądamy wierzchołki $i_j$ należące do kielicha i zaznaczmy wierzchołki z $\mathrm{\Gamma }(i_j)$,
• przeglądamy teraz wierzchołki grafu i tworzymy listę wierzchołków zaznaczonych --- to jest właśnie $\mathrm{\Gamma }(b)$,
• dodajemy $b$ jako sąsiada wierzchołków $\mathrm{\Gamma }(b)$.

Zauważmy, że każdy wierzchołek tylko raz może należeć do kielicha. Przejrzenie list $\mathrm{\Gamma }(i_j)$ i markowanie wierzchołków zajmie więc w sumie czas $O(n^2)$. Pozostałe czynności w zajmują zawsze czas $O(n)$ co w sumie daje czas $O(n^2)$.

Przejdźmy teraz do problemu rozwinięcia cykli. Samo rozwinięcie cykli może być zrealizowane w czasie $O(n^2)$, poprzez przejrzenie wszystkich wierzchołków oraz krawędzi w grafie w trakcie którego usuwamy wszystkich pseudowierzchołki i markujemy nieaktywne elementy grafu jako aktywne. Robiąc to musimy jednak pamiętać także o rozwijaniu ścieżki $P=P_1+P_2+x_1{x}_2$. Najpierw przechodząc tą ścieżkę markujemy wszystkie wierzchołki $v$ do niej należące i zapisujemy dla niech w zmiennej $p(v)$ ich poprzedników na ścieżce oraz w zmiennej $n(v)$ ich następników. Jeżeli teraz rozwijamy pseudowierzchołek $v$, który leży na ścieżce, to:

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

W ten sposób dla każdego rozwijanego kielicha musimy wykonać $O(n)$ dodatkowych operacji, co przy rozwijaniu $n-1$ kielichów daje złożoność $O(n^3)$.