java - Ford-Fulkerson irregularity (multiple vertices vs. backflow)

Question

I've thus far been working with graphs whose vertices have only one directed edge between them. For all the examples I've used to test my implementation, the right answer has been produced. When I use a graph containing vertices which have an edge running both directions, however, I don't produce the right answer. I've been treating such an edge running backward as the backflow between those two vertices, as it seems that the backflow and a different "pipe" running backward would end up being equivalent. Is my assumption here wrong?

Answer 1

容量 'a' と 'b' を持つ 2 つのエッジが 1 つのエッジに U--[a]-->V相当V--[b]-->Uするという仮定U--[a-b]-->Vは正しくありません。a > b と仮定すると、-b までの負のフローは、最初のケースでは合法ですが、2 番目のケースでは違法です。

同じ方向のエッジの流動容量のみを合計できます。下のグラフでは、E から F へ、および F から E への 2 つの反対のパイプを追加すると、それらがグラフから消え、最適解が変化します。