THE MAX-FLOW MIN-CUT THEOREM SEBASTIAN VATTAMATTAM Definition 0.1. E V × V,G = (V,E) -directed graph. Definition 0.2. x, y 2 V.x = x0, e1, x1, e2, ...en, xn = y -an x − y walk. Definition 0.3. (1) x − y walk is a trail if no edge is repeated. A closed trail is a circuit. (2) x−y walk is a path if no vertex is repeated. A closed path is a cycle. Definition 0.4. An undirected graph G = (V,E) is conneccte if any two vertices are joined by a path. Definition 0.5. Multigraph -having more than one edge joining a pair of vertices. Definition 0.6. G1 = (V1,E1) is a subgraph of G = (V,E) if V1 V,E1 E and every edge in E1 joins vertices in V1 Definition 0.7. Complete graph Kn Definition 0.8. Complement ¯Gof G = (V,E), with n vertices -obtained be deleting from Kn the edges of G. K¯n -null graph. Definition 0.9. G1 = (V1,E1),G2 = (V2,E2) are isomorphhi if there is a function f : V1 ! V2such that (1) f is bijective, and (2) 8(a, b) 2 E1, (f(a), f(b)) 2 E2 Definition 0.10. G is undirected. deg(v) -number of edges incident with v. Date: 09 -03 -10. 12 SEBASTIAN VATTAMATTAM Definition 0.11. Euler Circuit -a circuit that passes through every edge exactly once.Such an open trail is an Euler Trail. Definition 0.12. (1) Number of incoming edges -indegrre -id(v) (2) Number of outgoing edges -outdegree -od(v) Definition 0.13. Planar graph. Definition 0.14. Bipartite Graph, and Complete Bipartite Graph Km,n Definition 0.15. Induced subgraph. Definition 0.16. (1) v 2 V, V1 = V − v,E1 the set of edges not incident with v. Then G − v = (V1,E1) (2) e 2 E,E1 = E − e, V1 = V,G − e = (V1,E1) Definition 0.17. (G) -the number of components of G. Definition 0.18. N = (V,E), a loop-free connected digrrap is a network if (1) there is a unique a 2 V , called the source, with id(a) = 0, (2) there is a unique z 2 V , called the sink, with od(z) = 0, and (3) there is a function c : E ! {0, 1, 2, ...}. If e = (v,w) 2 E, c(e) = c(v,w) is called the capacity of e. 1 Example 0.1. Example 13.5 in the Book [1]. In Figure 1, c(a, b) = 5, c(d, z) = 5 Definition 0.19. If N = (V,E) is a network, a function c : E ! {0, 1, 2, ...} is called a flow for N, if (1) f(e) c(e), 8e 2 E, and 1id is indegree, od is outdegreeMAX-FLOW 3 Figure 1. Network (2) 8v 2 V, v 6= a, Xw2V f(w, v) =Xw2V f(v,w) (If (w, v) /2 E, f(w, v) = 0) In Figure 2 (a), c(a, b) = 5, f(a, b) = 3 Xv2V f(v, g) = f(a, g) = 5,Xv2V f(g, v) = f(g, b)+f(g, h) = 2+2 = 4 So, f is not a flow. In Figure 2 (b) f is a flow. Definition 0.20. Let f be a flow for the network N = (V, e). (1) e 2 E is saturated if f(e) = c(e). (2) If a is the source, then val(f) = Pv2V f(a, v) is called the value of the flow. In Figure 2 (b), c(h, d) = f(h, d) = 2. So, (h, d) is saturatted val(f) =Xv2V f(a, v) = f(a, b) + f(a, g) = 3 + 5 = 84 SEBASTIAN VATTAMATTAM Figure 2. Network Definition 0.21. For a network a flow that attains the greatest possible value, is called a maximal flow. The Labeling Procedure Network N = (V,E). Step 1: Define f(e) = 0, 8e 2 E Step 2: Label the source a ! a(−,1) Step 3: 8(a, x) 2 E label x as follows: (1) If c(a, x) > f(a, x), define (x) = c(a, x)−f(a, x) and label x ! x(a+, (x)) (2) If c(a, x) = f(a, x) leave x unlabeled. Step 4: If a 6= x 2 V and x is labeled, and there is (x, y) 2 E where y is not labeled, label y as follows: (1) If c(x, y) > f(x, y), define (y) = min{(x), c(x, y)− f(x, y)} and label y ! y(x+, (y)) (2) If c(x, y) = f(x, y) leave y unlabeled.MAX-FLOW 5 Step 5: If a 6= x 2 V and x is labeled, and there is (y, x) 2 E where y is not labeled, label y as follows: (1) If f(y, x) > 0, define (y) = min{(x), f(y, x)} and label y ! y(x−, (y)) (2) If f(y, x) = 0 leave y unlabeled. Whenever z is labeled, find the a−z path in which every vertex is labeled and add 4(z) to each of its edges. When the algorithm is over there may arise two cases: Case 1: z is labeled. The resulting network gives the Max-flow. Case 2: z is not labeled. Then the network gets disconnnecte into two components. Let P be the set of vertices containing a and ¯ P = V −P. Find c(P, ¯ P) = Px2P,y2 ¯ P c(x, y) and check whether it equalsPx2V f(x, z). References [1] Ralph P. Grimaldi,Discrete and Combinaorial Mathmatics,Fourth Edition, Pearson Eucation Asia, 1999 Mary Bhavan, Ettumanoor E-mail address: vattamattam@gmail.com