Maximal Graph-Algorithmus fließen

Question

Weiß jemand, welcher Algorithmus verwendet werden soll, die maximale Strömung in der nicht orientierte Graph?

zu finden

Soweit ich verstehe, die nicht orientierte Netzwerk hier stellt sich grundsätzlich die Grafik in ein Multigraph mit den Eckpunkten verbunden durch zwei „normale“ Rippen und zwei „fake“ Rippen, die sind, zum Beispiel in dem Ford-Fulkerson Algorithmus verwendet wird.

Aber wie soll ich den Fall eines Multigraphen umgehen?

Answer 1

Wenn Sie nicht orientierten Kante

     5
* ------ *

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

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

Ford-Fulkerson Methode funktioniert auf solchen Graphen perfekt.