Maximal flow graph algorithm
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 t开发者_C百科he 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.
精彩评论