Zaawansowane algorytmy i struktury danych/Ćwiczenia 9

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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