Zaawansowane algorytmy i struktury danych/Ćwiczenia 9

From Studia Informatyczne

Spis treści

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.