Zaawansowane algorytmy i struktury danych/Ćwiczenia 7

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_{in,out}^k=(V_{in}^k\cup V_{out}^k,E_{in,out}^k)$ w następujący sposób:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \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_{in,out}^2$ skonstruowany na podstawie grafu $G$.

Zauważ, że jeżeli w grafie $G_{in,out}^k$ 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_{in,out}^k$ 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_{in,out}^k$ zawiera doskonałe skojarzenie. Liczbę $k$ można też wyznaczyć, nie używając wyszukiwania binarnego. Rozważmy graf $G_{in,out}^{|V|}$, 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_{in,out}^{|V|}$ skojarzenie o liczności $|V|-k$. Weźmy teraz maksymalne skojarzenie w $G_{in,out}^{|V|}$ 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.

Plik:Zasd planar-path-transformation.png

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^{\prime }$ liczba wierzchołkowo rozłącznych ścieżek jest równa maksymalnemu przepływowi w oryginalnym grafie. Co więcej, graf $G^{\prime }$ jest planarny. Pozostaje nam wykonać teraz na $G^{\prime }$ 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=\mathrm{\varnothing }$, 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^{\prime }$ 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^{\prime }$ jest silnie spójny.