Flujo máximo algoritmo gráfico

Question

¿Alguien sabe qué algoritmo debe utilizarse para encontrar el flujo máximo en el no orientada gráfica?

Por lo que yo entiendo, la red no orientada aquí básicamente convierte el gráfico en una multigrafo con vértices conectados por dos "ordinarios" costillas y dos "falsos" costillas, que son, por ejemplo utilizado en el algoritmo Ford-Fulkerson.

Pero, ¿cómo debería manejar el caso de un multigrafo?

Answer 1

Si usted tiene borde no orientada

     5
* ------ *

A continuación, se puede convertir en dos bordes orientados:

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

funciona el método de Ford-Fulkerson en tales gráficos perfectamente.