Maximal débit algorithme de graphique

Question

ce que quelqu'un sait quel algorithme doit être utilisé pour trouver le flux maximal dans le non orienté graphique?

Pour autant que je comprends, le réseau non orienté ici tourne essentiellement le graphique dans un multigraphe dont les sommets sont reliés par deux « ordinaires » côtes et deux « faux » côtes, qui sont par exemple utilisés dans l'algorithme de Ford-Fulkerson.

Mais comment dois-je traiter le cas d'un multigraphe?

Answer 1

Si vous avez bord non orienté

     5
* ------ *

alors vous pouvez le transformer en deux arêtes orientées:

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

méthode Ford-Fulkerson travaux sur ces graphiques parfaitement.