Zaawansowane algorytmy i struktury danych/Ćwiczenia 7

From Studia Informatyczne

Spis treści

Zadanie 1

Masz dany graf G=(V, E) wraz z dwoma wybranymi wierzchołkami s,t \in V. Pokaż, jak używając algorytmu Hopcrofta-Karpa wyznaczyć maksymalną liczbę wierzchołkowo rozłącznych ścieżek z s do t. Wierzchołki s i t będą oczywiście wspólne dla tych ścieżek.

Rozwiązanie

Na podstawie grafu G=(V,E) konstruujemy graf dwudzielny G^k_{in,out} = (V^k_{in} \cup V^k_{out}, E^k_{in,out}) w następujący sposób:

\begin{array}{r@{}c@{}l} V^k_{out} &:=& \{v_{out} : v \in V\, \ v\neq s\} \cup \{s_{out}^{i} : 1\le i \le k\},\\ V^k_{in} &:=& \{v_{in} : v \in V\, \ v\neq t\} \cup \{t_{in}^{i} : 1\le i \le k\},\\ E^k_{out,in} &:=& \{v_{out} u_{in} : (v,u) \in V, \ v \neq s,\ u\neq t\} \cup\\ &\cup& \{v_{out}v_{in} : v \in V\}\cup\\ &\cup& \{s_{out}^i u_{in} : (s,u) \in V, \ 1\le i \le k\}\cup\\ &\cup& \{v_{out} t_{in}^i : (v,t) \in V, \ 1\le i \le k\}.\\ \end{array}

Konstrukcja ta jest przedstawiona na poniższym rysunku a) przykładowy graf G b) graf G^2_{in,out} skonstruowany na podstawie grafu G.


Zauważ, że jeżeli w grafie G^{k}_{in,out} istnieje doskonałe skojarzenie, to w grafie G istnieje k rozłącznych wierzchołkowo ścieżek z s do t. Jest tak, ponieważ każde doskonałe skojarzenie w G^k_{in,out} koduje zbiór wierzchołkowo rozłącznych ścieżek z s do t. Krawędzie wybrane do doskonałego skojarzenia M kodują krawędzie wchodzące do i wychodzące z wierzchołka v. Krawędź wchodząca z v jest kodowana przez krawędź M kojarzącą wierzchołek v_{in}, a krawędź wychodząca kodowana jest przez krawędź kojarzącą v_{out}. Odczytując skojarzenie M w ten sposób dostajemy zbiór ścieżek, zaczynających się w s i kończących w t, oraz ewentualnie pewien zbiór cykli. W drugą stronę łatwo zauważyć, że z każdego zbioru k rozłącznych ścieżek możemy skonstruować doskonałe skojarzenie w grafie G.

W celu wyznaczenia liczby wierzchołkowo rozłącznych ścieżek w G, możemy przy pomocy binarnego wyszukiwania znaleźć największe k, dla którego G^k_{in,out} zawiera doskonałe skojarzenie. Liczbę k można też wyznaczyć, nie używając wyszukiwania binarnego. Rozważmy graf G^{|V|}_{in,out}, oraz załóżmy, że w G jest w nim k wierzchołkowo rozłącznych ścieżek. Używając kodowania opisanego powyżej możemy skonstruować w G^{|V|}_{in,out} skojarzenie o liczności |V| - k. Weźmy teraz maksymalne skojarzenie w G^{|V|}_{in,out} i przyjrzyjmy się zbiorowi ścieżek, jaki ono koduje w G. Zauważmy, że jeżeli ścieżka wychodząca z wierzchołka s urywa się nagle, to można ja usunąć nie zmieniając liczności skojarzenie M, te same wierzchołki można skojarzyć krawędziami postaci v_{out}v_{in}, które odpowiadają jednoelementowym cyklom.

Zadanie 2

Masz daną sieć przepływową G=(V, E) wraz z dwoma wybranymi wierzchołkami s,t \in V, w której wszystkie przepustowości krawędzi wynoszą 1. Pokaż, jak używając algorytmu Hopcrofta-Karpa wyznaczyć maksymalny przepływ z s do t w sieci G.

Rozwiązanie

Graf krawędziowy dla grafu G=(V,E) to graf G_L=(E,E_L), w którym wierzchołkami są krawędzie grafu G. Natomiast zbiór krawędzi w grafie G_L to zbiór par krawędzi sąsiednich w G. Dodajmy do grafu G dwie nowe krawędzie: krawędź e_s wchodzącą do s i krawędź e_t wychodzącą z t. Skonstruujemy teraz z G graf G_L. Łatwo zauważyć teraz, że maksymalna liczba wierzchołkowo rozłącznych ścieżek w G odpowiada maksymalnemu przepływowi w sieci G.


Zadanie 3

Masz daną planarną sieć przepływową G=(V, E) wraz z dwoma wybranymi wierzchołkami s,t \in V, w której wszystkie przepustowości krawędzi wynoszą 1. Pokaż, jak rozwiązać problem wyznaczenia maksymalnego przepływu w sieci G poprzez znalezienie maksymalnego skojarzenia w planarnym grafie dwudzielnym, tzn. pokaż konstrukcję taką, jak ta przedstawiona w Zadaniu 1 i 2, ale zachowującą planarność grafu.

Rozwiązanie

Dla każdego wierzchołka trzeba wykonać transformację przedstawioną na poniższym rysunku a) transformowany wierzchołek b) podgraf skonstruowany na podstawie tego wierzchołka, który łączy się z tymi samymi krawędziami.

W transformacji tej zamieniamy wierzchołek o stopniu d na \lfloor \frac{d}{2} \rfloor skierowanych cykli zawierających d wierzchołków, po jednym dla każdej krawędzi. Następnie wierzchołki odpowiadające wchodzącej krawędzi łączymy skierowaną ścieżką, skierowanie tej ścieżki jest zgodne z kierunkiem tej krawędzi. Zauważ, że w tak skonstruowanym grafie G' liczba wierzchołkowo rozłącznych ścieżek jest równa maksymalnemu przepływowi w oryginalnym grafie. Co więcej, graf G' jest planarny. Pozostaje nam wykonać teraz na G' transformację z Zadania 1. Zauważmy, że także po jej wykonaniu graf pozostanie planarny.

Zadanie 4

Masz dany graf G=(V_1 \cup V_2, E) dwudzielny. Pokaż, jak używając algorytmu Hopcrofta-Karpa wyznaczyć minimalne pokrycie wierzchołkowe tego grafu.

Rozwiązanie

Znajdźmy maksymalne skojarzenie M w grafie G przy pomocy algorytmu Hopcrofta-Karpa. Liczność skojarzenia M na pewno jest nie większa niż liczność minimalnego pokrycia wierzchołkowego, ponieważ co najmniej jeden koniec każdej krawędzi skojarzenia musi być wzięty do minimalnego pokrycia wierzchołkowego. Pokażemy teraz, że zachodzi równość, tzn. liczność maksymalnego skojarzenia w grafie dwudzielnym jest równa liczności minimalnego pokrycia wierzchołkowego tego grafu. Dowód ten będzie konstrukcyjny, więc automatycznie dostaniemy algorytm wyznaczający minimalne pokrycie wierzchołkowe.

Skierujmy krawędzie skojarzenia od V_2 do V_1, a wszystkie pozostałe krawędzie od V_1 do V_2. Niech R_1 i R_2 będą zbiorami wierzchołków wolnych odpowiednio w V_1 i V_2. Niech Z oznacza zbiór wierzchołków osiągalnych w tym grafie z R_1. Zauważmy, że Z \cap R_2 = \emptyset, ponieważ w innym wypadku ścieżka z R_1 do R_2 stanowiłaby ścieżkę powiększającą względem maksymalnego skojarzenia M. Niech L:= (V_2 \cap Z) \cup (V_1 - Z). Łatwo zauważyć, że liczność L jest równa liczności zbioru M oraz że L jest pokryciem wierzchołkowym.

Zadanie 5

Niech G = (V_1 \cup V_2,E) będzie grafem dwudzielnym. O krawędzi e\in E mówimy, że jest dozwolona w G jeżeli istnieje doskonałe skojarzenie M zawierające e. Dwudzielny graf G nazywamy natomiast elementarnym jeżeli wszystkie krawędzie są dozwolone. Zaproponuj, jak wykorzystując algorytm Hopcrofta-Karpa sprawdzić, czy G jest elementarny?


Wskazówka

Znajdźmy doskonałe skojarzenie M w grafie G przy pomocy algorytmu Hopcrofta-Karpa. Jeżeli G nie zawiera doskonałego skojarzenia, to na pewno nie jest elementarny. Skonstruujmy graf G' z G poprzez skierowanie krawędzi skojarzenia od V_2 do V_1, a wszystkich pozostałych krawędzi od V_1 do V_2. Łatwo jest pokazać, że graf G jest elementarny wtedy i tylko wtedy, gdy graf G' jest silnie spójny.