Max Flow - Min Cut

by Laurie L. Lacey, Ph.D., Schenectady County Community College, Schenectady NY, USA, laceyll@gw.sunysccc.edu, 2004 Laurie L. Lacey

NOTE: This worksheet constructs a maplet that can be used by the student in a Discrete math class to investigate network flows.  

Introduction

When this maplet is run, it allows the student to examine the Max Flow - Min Cut Theorem.  Students can compare the value of the maximum flow to the value of the minimum cut, and determine the edges of the minimum cut as well as the saturated edges. Students can observe the graph with the minimum cut edges removed.  The maplet was constructed using Maple 9.5.  A sample graph has been loaded into the first textfield so the student can see the syntax.

>

restart:

>	restart;with(Maplets[Elements]): with(networks):#The networks package is accessed so that we may examine the graphs.

>	#alter the graph to delete the edges of the minimum cut

>

Mincutplot := proc() local G,s,t,f,H;                                                               G:= Maplets[Tools][Get]('TF1'::algebraic);                                                              s:= Maplets[Tools][Get]('TF2'::algebraic);                                                              t:= Maplets[Tools][Get]('TF3'::algebraic);           f:=edges(G) minus mincut(G,s,t);               H:=induce(f,G):draw(H); end proc:

>	#calculate the maximum flow for the given network

>

Flow := proc()         local G,s,t;                                                                                    G:= Maplets[Tools][Get]('TF1'::algebraic);                                                s:= Maplets[Tools][Get]('TF2'::algebraic);                                                t:= Maplets[Tools][Get]('TF3'::algebraic);                 flow(G,s,t);   end proc:

>	#calculate the saturated edges of the maximum flow

>

SaturatedEdges := proc()         local G,s,t,eset,comp;           eset := 'eset': comp := 'comp':                                                        G:= Maplets[Tools][Get]('TF1'::algebraic);                                      s:= Maplets[Tools][Get]('TF2'::algebraic);                                                t:= Maplets[Tools][Get]('TF3'::algebraic);                 flow(G,s,t,eset); eset; end proc:

>	#calculate the saturated vertices of the maximum flow

>

SaturatedVertices := proc()         local G,s,t,eset,comp;             eset := 'eset': comp := 'comp':                                                                                                 G:= Maplets[Tools][Get]('TF1'::algebraic);                                                s:= Maplets[Tools][Get]('TF2'::algebraic);                                                t:= Maplets[Tools][Get]('TF3'::algebraic);              flow(G,s,t,eset,comp); comp; end proc:

>	#calculate the edges of the minimum cut

>

MinCut := proc()         local G,s,t;                                                                                                            G:= Maplets[Tools][Get]('TF1'::algebraic);                                                s:= Maplets[Tools][Get]('TF2'::algebraic);                                                t:= Maplets[Tools][Get]('TF3'::algebraic);               mincut(G,s,t);   end proc:

>	#calculate the value of the minimum cut for comparison with value of maximum flow

>

MinCutValue := proc()           local G,s,t,vf;vf:='vf':                                                                          G:= Maplets[Tools][Get]('TF1'::algebraic);                                                s:= Maplets[Tools][Get]('TF2'::algebraic);                                                t:= Maplets[Tools][Get]('TF3'::algebraic);                      mincut(G,s,t,vf):vf;   end proc:

>	#The Maximum Flow - Minimum Cut Maplet

>

maplet := Maplet( Window( 'title'="Max Cut-Min Flow" ,BoxColumn('vscroll'='always',                   BoxColumn(["Enter the graph with capacities ",                                    TextField['TF1'](                                  value="graph({a,2,3,z,4,5,6},{[a,2],[a,5],[a,4],[4,2],[2,3],                                 [4,5],[5,6],[6,3],[4,z],[3,z],[6,z]},                                 weights=[3,5,2,1,2,2,3,2,3,4,3])",                         ('width' = 70))                ],                   BoxRow(["Enter the source vertex: ",TextField['TF2'](value='a')],                         ["Enter the sink vertex: ",TextField['TF3'](value='z')]),                TextBox['TB1'](),TextBox['TB2']()),                              BoxRow( Plotter['PL1']('height'=300,'width'=300),                Plotter['PL2']('height'=300,'width'=300)),                                                                                                                          [                                                                                     Button("Draw", Evaluate('PL1' = 'draw(TF1)') ),                                                                                        Button("Clear",                           Action(SetOption('TF1' = ""),                                 SetOption('TF2'=""),SetOption('TF3'=""),SetOption('TB1'=""),                                 SetOption('TB2'=""),Evaluate( 'PL1' = "" ),Evaluate('PL2'=""))),                                 Button("Flow",Evaluate( 'TB1'="Flow",Argument('TF1'),Argument('TF2'),Argument('TF3'))),                                                Button("Satedges", Evaluate('TB2'="SaturatedEdges",Argument('TF1'),Argument('TF2'),Argument('TF3'))),               Button("Satverts",Evaluate('TB2'="SaturatedVertices",                         Argument('TF1'),Argument('TF2'),Argument('TF3'))),                                                                                                  Button("Min Cut",Evaluate( 'TB1'="MinCut",Argument('TF1'),Argument('TF2'),Argument('TF3'))),                                            Button("Val Min Cut",Evaluate('TB2'="MinCutValue",Argument('TF1'),                         Argument('TF2'),Argument('TF3'))),                                                                                              Button("Display Min Cut ",                         Evaluate( 'PL2'="Mincutplot",Argument('TF1'),Argument('TF2'),Argument('TF3'))),                                   Button("Help", RunDialog('MD1')),                Button("Close", Shutdown(['TF1']))   ]  )),     MessageDialog['MD1']( "For example, enter graph({1,2,3,4},{{1,2},{3,4},{2,3},{2,4}},weights=[1,2,3,4]), or else, enter petersen(), cube(3), etc.", 'type'='information' )                                    ):       Maplets[Display](maplet);

This is a very simple maplet that is designed to introduce the Max Flow Min Cut Theorem.   The reader is encouraged to add basic error routines and to modify the Maplet to accomodate applications of the Theorem.  The reader should note that the graphs are assumed to not be multigraphs and to not have multiple sources or sinks.  The capacities were also assumed to be integers.  The reader should further note that Maple tends to number the edges in the order they are entered.  The notation and format were adapted from the Maplet Tutorial available with Maple 9.5 [1].  My thanks to Goodaire and Parmenter [2] for writing a text with a number of examples that helped me test the Maplet.

[1] Examples, Maplet Tutorial , Maple 9.5,  Maplesoft, A Division of Waterloo Maple Inc. 2004.

[2] Goodaire, E. and Parmenter, M., Discrete Mathematics with Graph Theory, second edition, Prentice Hall, Upper Saddle River, NJ, 2002, pp. 448-454.

Disclaimer: While every effort has been made to validate the solutions in this worksheet, Waterloo Maple Inc. and the contributors are not responsible for any errors contained and are not liable for any damages resulting from the use of this material.