Алгоритм максимального потока

Question

Кто-нибудь знает, какой алгоритм следует использовать для нахождения максимального потока в неориентированном графике?

Насколько я понимаю, неориентированная сеть здесь в основномпревращает график в мультиграф с вершинами, соединенными двумя "обычными" ребрами и двумя "поддельными" ребрами, которые, например, используются в алгоритме Ford-Fulkerson.

Но как мне справиться со случаем мультиграфа?

Answer 1

Если у вас неориентированное ребро

     5
* ------ *

тогда вы можете превратить его в два ориентированных ребра:

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

Метод Форда-Фулкерсона отлично работает на таких графиках.