Zaawansowane algorytmy i struktury danych/Ćwiczenia 9: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
Linia 2: Linia 2:
 
{{kotwica|zadanie 1|}}
 
{{kotwica|zadanie 1|}}
  
 
+
Udowodnij [[../Wykład 8#lemat 1|Lemat 1]] z tego wykładu.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 +
Wszystkie równości w lemacie można udowodnić korzystając ze wzoru:
 +
 +
{{wzor2|1=
 +
<math>
 +
f(X,Y) = \sum_{x \in X} \sum_{y \in Y} f(x,y).
 +
</math>
 +
}}
  
 
</div>
 
</div>
Linia 12: Linia 19:
 
== Zadanie 2 ==
 
== Zadanie 2 ==
 
{{kotwica|zadanie 2|}}
 
{{kotwica|zadanie 2|}}
 
+
W problemie '''maksymalnego przepływu z wieloma źródłami i ujściami''' mamy daną sieć przepływową <math>G</math>, zbiór źródeł <math>s_1, \ldots, s_m</math> oraz zbiór ujść <math>t_1,\ldots,t_n</math> i chcemy wyznaczyć maksymalny sumaryczny przepływ ze źródeł <math>s_1, \ldots, s_m</math> do ujść <math>t_1,\ldots,t_n</math>. Zaproponuj efektywny algorytm rozwiązujący ten problem?
 
 
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
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 <math>s</math> i krawędzie <math>(s,s_i)</math> o przepustowości <math>c(s,s_i) = \infty.</math>, dla <math>i = 1,\ldots,m</math>. Dodajemy także superujście <math>t</math> wraz z krawędziami <math>(t_i,t)</math> o przepustowości <math>c(t_i,t)=\infty</math> dla <math>i=1,\ldots, n</math>. Widzimy teraz, że każdy przepływ w sieci oryginalnej odpowiada przepływowi w nowo utworzonej sieci.
 
</div>
 
</div>
 
</div>
 
</div>
 
  
 
== Zadanie 3 ==
 
== Zadanie 3 ==
 
{{kotwica|zadanie 3|}}
 
{{kotwica|zadanie 3|}}
 +
Załóżmy, że w problemie maksymalnego przepływu z wieloma źródłami i ujściami, z każdego źródła <math>s_i</math> wypływa dokładnie <math>p_i</math> jednostek przepływu. Natomiast do każdego ujścia <math>t_i</math> musi wpłynąć dokładnie <math>q_i</math> jednostek przepływu tak, że <math>\sum_{i=1}^m p_i = \sum_{i=1}^{n}q_i</math>. 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?
  
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
Podobnie jak w rozwiązaniu zadania 2 dodajemy do sieci przepływowej nowe superźródło <math>s</math> wraz z krawędziami  <math>(s,s_i)</math>, oraz nowe superujście wraz z krawędziami <math>(t_i,t)</math>. Jednak przepustowości nowo dodanych krawędzi zadajemy tak aby <math>c(s,s_i) = p_i </math> oraz <math>c(t_i,t) = q_i</math>. 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 <math>\sum_{i=1}^m p_i = \sum_{i=1}^{n}q_i</math> 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ż <math>\sum_{i=1}^m p_i = \sum_{i=1}^{n}q_i</math>, ponieważ taka jest przepustowość rozcięcia <math>(s,V-s)</math>.
 +
</div>
 +
</div>
  
 +
== Zadanie 4 ==
 +
{{kotwica|zadanie 4|}}
 +
'''Spójność krawędziową''' nieskierowanego grafu definiujemy jako minimalną liczbę krawędzi <math>k</math> które muszą zostać usunięte z grafu żeby przestał on być spójny. Na przykład spójność krawędziowa drzewa wynosi <math>1</math>, natomiast spójność krawędziowa cyklu wynosi <math>2</math>. Pokaż jak wyznaczyć spójność krawędziową nieskierowanego grafu <math>G=(V,E)</math> poprzez <math>|V|</math> krotne uruchomienie algorytmu wyznaczającego maksymalny przepływ w grafie na sieciach przepływowych o <math>O(|V|)</math> wierzchołkach i <math>O(|E|)</math> krawędziach.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
Niech <math>S</math> będzie zbiorem krawędzi o liczności <math>k</math> których usunięcie rozspójnia <math>G</math>, tzn. po usunięciu <math>S</math> <math>G</math> rozpada się na dwie składowe <math>V_1</math> i <math>V_2</math> między którymi nie prowadzi żadna krawędź i <math>V_1 \cup V_2 = V </math>. Jeżeli założymy, że każda krawędź w grafie ma przepustowość <math>1</math>, to <math>(V_1,V_2)</math> jest rozcięciem grafu o przepustowości <math>k</math>. Zauważmy, że dowolny wierzchołek <math>v</math> musi należeć do <math>V_1</math> bądź <math>V_2</math>.
 
</div>
 
</div>
 
</div>
 
</div>

Aktualna wersja na dzień 15:47, 28 wrz 2006

Zadanie 1

Udowodnij Lemat 1 z tego wykładu.

Rozwiązanie

Zadanie 2

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

Rozwiązanie

Zadanie 3

Załóżmy, że w problemie maksymalnego przepływu z wieloma źródłami i ujściami, z każdego źródła wypływa dokładnie jednostek przepływu. Natomiast do każdego ujścia musi wpłynąć dokładnie jednostek przepływu tak, że . 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

Zadanie 4

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

Rozwiązanie