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},\ldots ,s_{m}$ oraz zbiór ujść $t_{1},\ldots ,t_{n}$ i chcemy wyznaczyć maksymalny sumaryczny przepływ ze źródeł $s_{1},\ldots ,s_{m}$ do ujść $t_{1},\ldots ,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})=\infty .$, dla $i=1,\ldots ,m$. Dodajemy także superujście $t$ wraz z krawędziami $(t_{i},t)$ o przepustowości $c(t_{i},t)=\infty$ dla $i=1,\ldots ,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}$.