Question: Finding pairwise vertex disjoint paths between two vertices with maximum size.

Vertex disjoint paths are paths that only share their first and last vertices.  In Maple, we can compute the maximum number of pairwise vertex disjoint paths from x to y by the function MaxFlow.  

For example:

with(GraphTheory):
with(SpecialGraphs):
g:=IcosahedronGraph():
HighlightVertex(g, {1,7},"DodgerBlue"):
DrawGraph(g);
g1:=MakeWeighted(g);
mxf:=MaxFlow(g1,1,7)

5

Matrix(12, 12, [[0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]])

So  we know that the maximum number  of vertex-disjoint paths between vertices "1" and "7" is 5. 

But can we obtain more information from MaxFlow, such as finding  five (i.e., the maximum number) vertex-disjoint paths between vertices "1" and "7" ? (These five paths may not be unique.)

Here is a set of five vertex-disjoint paths connecting vertices "1" and "7" that I observed manually, each marked with a different color.

Please Wait...