sieć Modelowanie jako skierowany graf

Question

Mam sieć, która mogłaby wyglądać następująco:

Zasadniczo chcę wiedzieć minimalną liczbę zielone kółka, które można odłączyć źródło i drenażu jeśli usunięty/wyłączony. (w tym przypadku 1)
Z powodzeniem wdrożyłem już algrorith Edmonds-Karp, ale nie wiem jak modelować sieć z ukierunkowanymi krawędziami, więc uzyskam pożądany rezultat.
Jeśli po prostu zastąpię każde połączenie między węzłami dwoma przeciwległymi skierowanymi krawędziami o pojemności 1, otrzymam maksymalny przepływ 2 z EdmondsKarp, ale muszę tylko usunąć 1 zielone koło, aby zerwać sieć.
Jak mogę modelować moją sieć jako węzły i kierować krawędzie?

Answer 1

Możesz zredukować ten problem do standardowego problemu z wykreślaniem s-t w kierowanych wykresach, który następnie można rozwiązać np. według algorytmu Edmondsa-Karpa. Dla każdego wierzchołka v utwórz dwa wierzchołki v_in i v_out oraz krawędź skierowaną (v_in, v_out), a dla każdej krawędzi {v, w} dodaj dwie skierowane krawędzie (v_out, w_in) i (w_out, v_in). Nietrudno zauważyć, że maksymalny przepływ od s_in do t_out odpowiada minimalnemu przecięciu wierzchołka pomiędzy s i t.

Answer 2

Masz poprawnie określony maksymalny przepływ - 2 dla twojej sieci.

Z definicji flow network

Przepływ musi spełniać ograniczenie że ilość przepływu do węzła równa ilości przepływu z niego, wyjątkiem sytuacji, gdy jest to źródło, które ma więcej przepływ towarzyski, lub umywalka, która ma więcej przepływ przychodzące

tak na środkowym węźle masz 2 przepływ jako max (pochodzących i dzieje się). Zatem wiedza tylko o maksymalnym przepływie nie da odpowiedzi na minimalne cięcie.

Twierdzenie

max-min Przepływ cięte stany teorematu, że w sieci przepływu, maksymalna ilość przechodzenia od źródła do zlewu przepływu jest równa minimalnej pojemności który po usuwane w sposób szczególny z sieci powoduje sytuację że brak przepływu może przejść od źródła do zlewu

tak, tak, znasz ilość przepływu, którą musisz usunąć, ale nie wiesz, w jaki sposób ją usunąć. Myślę, że to nie jest tak banalne i że będziesz musiał szczególnie szukać minimalnego cięcia.