Question

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?

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top