Dear sage support
trying to learn how to use Sage in graph theory. I do not know the
terminology in this area of mathematics. Is the flow and the edge_cut
the two quantities which are equal by ford fulkerson theorem
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem ?
I consider the following graph. The flow is 30 (which is correct) and
the edge_cut is 31.
Many thanks
Robert
sage: g=DiGraph({0:{1:12,2:19},1:{2:9,3:8},2:{3:2,4:24},3:
{4:10,5:14,6:8},4:{1:12,6:20,7:5},5:{8:19},6:{5:8,7:7},7:{8:15}})
sage: g.flow(0,8) # maximal flow
30.0
sage: g.flow(0,8,value_only=False)[1].edges() # edges with flow
[(0, 1, 12), (0, 2, 18.0), (1, 2, 4.0), (1, 3, 8), (2, 3, 2), (2, 4,
20), (3, 5, 10), (4, 6, 15), (4, 7, 5), (5, 8, 18.0), (6, 5, 8), (6,
7, 7), (7, 8, 12)]
sage: g.edges() # original edges
[(0, 1, 12), (0, 2, 19), (1, 2, 9), (1, 3, 8), (2, 3, 2), (2, 4, 24),
(3, 4, 10), (3, 5, 14), (3, 6, 8), (4, 1, 12), (4, 6, 20), (4, 7, 5),
(5, 8, 19), (6, 5, 8), (6, 7, 7), (7, 8, 15)]
sage: g.edge_cut(0,8,use_edge_labels=True,value_only=False,
vertices=True)
(31.0, [(4, 7), (5, 8), (6, 7)], [[0, 1, 2, 3, 4, 5, 6], [7, 8]])
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
