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} }

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ż konstrukcje tak 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.

Plik: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 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$ to będą zbiory wierzchołków wolnych odpowiednio w $V_1$ i $V_2$. Niech $Z$ oznacza zbiór wierzchołków osiągalnych z 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.