Zaawansowane algorytmy i struktury danych/Ćwiczenia 9

Zadanie 1

Udowodnij Lemat 1 z tego wykładu.

Rozwiązanie

Wszystkie równości w lemacie można udowodnić korzystając ze wzoru:

$f(X,Y)=\sum _{x\in X}\sum _{y\in Y}f(x,y).$

Zadanie 2

W problemie maksymalnego przepływu z wieloma źródłami i ujściami mamy daną sieć przepływową $G$, zbiór źródeł $s_1,\dots ,s_m$ oraz zbiór ujść $t_1,\dots ,t_n$ i chcemy wyznaczyć maksymalny sumaryczny przepływ ze źródeł $s_1,\dots ,s_m$ do ujść $t_1,\dots ,t_n$. Zaproponuj efektywny algorytm rozwiązujący ten problem?

Rozwiązanie

Problem maksymalnego przepływu z wieloma źródłami i ujściami można w prosty sposób zredukować do standardowego problemu przepływu i rozwiązać przy pomocy dowolnego algorytmu dla tego problemu. W tym celu musimy dodać dodatkowe superźródło $s$ i krawędzie $(s,s_i)$ o przepustowości $c(s,s_i)=\mathrm{\infty }$, dla $i=1,\dots ,m$. Dodajemy także superujście $t$ wraz z krawędziami $(t_i,t)$ o przepustowości $c(t_i,t)=\mathrm{\infty }$ dla $i=1,\dots ,n$. Widzimy teraz, że każdy przepływ w sieci oryginalnej odpowiada przepływowi w nowo utworzonej sieci.

Zadanie 3

Załóżmy, że w problemie maksymalnego przepływu z wieloma źródłami i ujściami, z każdego źródła $s_i$ wypływa dokładnie $p_i$ jednostek przepływu. Natomiast do każdego ujścia $t_i$ musi wpłynąć dokładnie $q_i$ jednostek przepływu tak, że $\sum _{i=1}^m{p}_i=\sum _{i=1}^n{q}_i$. Pokaż jak sprowadzić problem znalezienia przepływu spełniającego te dodatkowe założenia do problemu znajdowania przepływu z jednym ujściem i źródłem?

Rozwiązanie

Podobnie jak w rozwiązaniu zadania 2 dodajemy do sieci przepływowej nowe superźródło $s$ wraz z krawędziami $(s,s_i)$, oraz nowe superujście wraz z krawędziami $(t_i,t)$. Jednak przepustowości nowo dodanych krawędzi zadajemy tak aby $c(s,s_i)=p_i$ oraz $c(t_i,t)=q_i$. Zauważmy teraz, że jeżeli istnieje przepływ spełniający dodatkowe założenia w oryginalnej sieci, to będzie istniał przepływ o wartości $\sum _{i=1}^m{p}_i=\sum _{i=1}^n{q}_i$ z superźródła do superujścia. Co więcej w przepływ z superźródła do superujścia nie może być większy niż $\sum _{i=1}^m{p}_i=\sum _{i=1}^n{q}_i$, ponieważ taka jest przepustowość rozcięcia $(s,V-s)$.

Zadanie 4

Spójność krawędziową nieskierowanego grafu definiujemy jako minimalną liczbę krawędzi $k$ które muszą zostać usunięte z grafu żeby przestał on być spójny. Na przykład spójność krawędziowa drzewa wynosi $1$, natomiast spójność krawędziowa cyklu wynosi $2$. Pokaż jak wyznaczyć spójność krawędziową nieskierowanego grafu $G=(V,E)$ poprzez $|V|$ krotne uruchomienie algorytmu wyznaczającego maksymalny przepływ w grafie na sieciach przepływowych o $O(|V|)$ wierzchołkach i $O(|E|)$ krawędziach.

Rozwiązanie

Niech $S$ będzie zbiorem krawędzi o liczności $k$ których usunięcie rozspójnia $G$, tzn. po usunięciu $S$ $G$ rozpada się na dwie składowe $V_1$ i $V_2$ między którymi nie prowadzi żadna krawędź i $V_1\cup V_2=V$. Jeżeli założymy, że każda krawędź w grafie ma przepustowość $1$, to $(V_1,V_2)$ jest rozcięciem grafu o przepustowości $k$. Zauważmy, że dowolny wierzchołek $v$ musi należeć do $V_1$ bądź $V_2$.