algorytm forda fulkersona istnienie digrafu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
niebieska_biedronka
Użytkownik
Użytkownik
Posty: 397
Rejestracja: 8 paź 2011, o 15:31
Płeć: Kobieta
Lokalizacja: Kraków
Podziękował: 96 razy
Pomógł: 19 razy

algorytm forda fulkersona istnienie digrafu

Post autor: niebieska_biedronka »

Stosując algorytm Forda - Fulkersona, sprawdź czy istnieje digraf D o następujących stopniach wierzchołków:
\(\displaystyle{ d^+(x_1) = 2, d^-(x_1) = 2, d^+(x_2) = 0, d^-(x_2) = 1,}\)
\(\displaystyle{ d^+(x_3) = 2, d^-(x_3) = 2, d^+(x_4) = 1, d^-(x_4) = 0}\)

Znam algorytm i potrafię wyznaczyć przepływ maksymalny, ale jak zastosować go do tego typu zadania?
ODPOWIEDZ