문제

Does someone know which algorithm should be used to find the maximal flow in the unoriented graph?

As far as I understand, the unoriented network here basically turns the graph into a multigraph with vertices connected by two "ordinary" ribs and two "fake" ribs, which are, for example used in the Ford-Fulkerson algorithm.

But how should I handle the case of a multigraph?

도움이 되었습니까?

해결책

If you have unoriented edge

     5
* ------ *

then you can turn it into two oriented edges:

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

Ford-Fulkerson method works on such graphs perfectly.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top