Algorithme de graphique de débit maximal

Question

Est-ce que quelqu'un sait quel algorithme devrait être utilisé pour trouver le débit maximal dans le graphique non orienté?

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 côtes « ordinaires » et deux « faux » côtes, qui sont, par exemple utilisé dans la Ford-Fulkerson algorithme.

Mais comment dois-je gérer le cas d'un multigraph?

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 fonctionne sur ces graphiques parfaitement.