Application of Maximum Flowsto Solve Other Optimization ProblemsProblemsLink Disjoint Routes3There are 3 arc-disjoint s-t pathsst1234567891011124Deleting 3 arcs disconnects s and tt125679101112s34 8Let S = {s, 3, 4, 8}. The only arcs from S to T = N\S are the 3 deleted arcs.5Node disjoint pathsTwo s-t paths P and P' f are said to be node-disjointif the only nodes in common to P and P' are s and t).How can one determine the maximum number of node disjoint s-t paths? Answer: node splittingTheorem. Let G = (N,A) be a network with no arc from s to t. The maximum number of node-disjoint paths from s to t equals the minimum number of nodes whose removal from G disconnects all paths from nodes s to node t.6There are 2 node disjoint s-t paths.st1234567891011127Deleting 5 and 6 disconnects t from s?t5679101112s1234 8Let S = {s, 1, 2, 3, 4, 8}There is no arc directed from S to T.Let T = {7, 9, 10, 11, 12, t}8MatchingsAn undirected network G = (N, A) is bipartite12345678910if N can be partitioned into N1and N2so that for every arc (i,j) either i N1and j N2.Amatching in N is a set of arcs no two of which are incident to a common node.Matching Problem: Find a matching of maximum cardinality9Transformation to a Max Flow Problem12345678910s tReplace original arcs by pairs, and put infinite capacity on original arcs.Each arc (s, i) has a capacity of 1.Each arc (j, t) has a capacity of 1.10Find a max flow12345678910s tThe maximum s-t flow is 4.The max matching has cardinality
View Full Document