Maximaler Fluss Graph Algorithmus

Question

Kennt jemand, welcher Algorithmus verwendet werden sollte, um den maximalen Fluss in der unorientierten Grafik zu finden?

Soweit ich das nicht orientierte Netzwerk hier im Grunde die Grafik in ein Multigraph dreht verstehen, mit zwei „normalen“ Rippen und zwei „fake“ Rippen verbunden Eckpunkt, die in dem zum Beispiel sind, verwendet Ford-Fulkerson Algorithmus.

Aber wie soll ich den Fall eines Multigraphen behandeln?

Answer 1

Wenn Sie Rand nicht orientiert haben

 5 
* ------ * 

dann können Sie es in zwei orientierten Kanten drehen:

 5 
    ------> 
*   * 
    <------ 
    5 

Ford-Fulkerson Methode funktioniert auf solche Graphen perfekt.