Zaawansowane algorytmy i struktury danych/Wykład 8

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 $O(|V{|}^3)$. 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 twierdzenie 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 potrzebujemy wprowadzić jedno oznaczenie. 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 $X\subseteq 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 aby udowodnienić, że skojarzenie $M$ jest maksymalne musimy pokazać zbiór $X\subseteq V$, 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 konstrukcje takiego zbioru, a tym samym pozwoli nam na udowodnienie następującej silniejszej wersji Lematu 1.

Twierdzenie 2 [Twierdzenie Berge'a]

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

$|M|=\underset{X\subseteq V}{\min }\frac{1}{2}(|V|-(c_0(G-X)-|X|)).$      (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 $G_M$ 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. 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 $L$,
• 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 Edmondsa 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 cyklu wszystkiem sąsiednim z nim wierzchołkom wydłużają się listy sąsiedztwa o $1$. Jednak w trakcie działania algorytmu wykonanych będzie co najwyżej $n/2$ kontrakcji więc listy te będą 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 cyklu 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 sciąganego cyklu. 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 wszystkie 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^2)$.