1Chapter 7Network FlowSlides by Kevin Wayne.Copyright © 2005 Pearson-Addison Wesley.All rights reserved.7.5 Bipartite Matching3Matching.! Input: undirected graph G = (V, E).! M " E is a matching if each node appears in at most edge in M.! Max matching: find a max cardinality matching.Matching4Bipartite MatchingBipartite matching.! Input: undirected, bipartite graph G = (L ! R, E).! M " E is a matching if each node appears in at most edge in M.! Max matching: find a max cardinality matching.1351'3'5'242'4'matching1-2', 3-1', 4-5'RL5Bipartite MatchingBipartite matching.! Input: undirected, bipartite graph G = (L ! R, E).! M " E is a matching if each node appears in at most edge in M.! Max matching: find a max cardinality matching.1351'3'5'242'4'RLmax matching1-1', 2-2', 3-3' 4-4'6Max flow formulation.! Create digraph G' = (L ! R ! {s, t}, E' ).! Direct all edges from L to R, and assign infinite (or unit) capacity.! Add source s, and unit capacity edges from s to each node in L.! Add sink t, and unit capacity edges from each node in R to t.Bipartite Matchings1351'3'5't242'4'11%RLG'7Theorem. Max cardinality matching in G = value of max flow in G'.Pf. &! Given max matching M of cardinality k.! Consider flow f that sends 1 unit along each of k paths.! f is a flow, and has cardinality k. !Bipartite Matching: Proof of Correctnesss1351'3'5't242'4'1 1%1351'3'5'242'4'G'G8Theorem. Max cardinality matching in G = value of max flow in G'.Pf. #! Let f be a max flow in G' of value k.! Integrality theorem $ k is integral and can assume f is 0-1.! Consider M = set of edges from L to R with f(e) = 1.– each node in L and R participates in at most one edge in M– |M| = k: consider cut (L ! s, R ! t) !Bipartite Matching: Proof of Correctness1351'3'5'242'4'Gs1351'3'5't242'4'1 1%G'9Def. A matching M " E is perfect if each node appears in exactly oneedge in M.Q. When does a bipartite graph have a perfect matching?Structure of bipartite graphs with perfect matchings.! Clearly we must have |L| = |R|.! What other conditions are necessary?! What conditions are sufficient?Perfect Matching10Notation. Let S be a subset of nodes, and let N(S) be the set of nodesadjacent to nodes in S.Observation. If a bipartite graph G = (L ! R, E), has a perfectmatching, then |N(S)| # |S| for all subsets S " L.Pf. Each node in S has to be matched to a different node in N(S).Perfect MatchingNo perfect matching:S = { 2, 4, 5 }N(S) = { 2', 5' }.1351'3'5'242'4'LR11Marriage Theorem. [Frobenius 1917, Hall 1935] Let G = (L ! R, E) be abipartite graph with |L| = |R|. Then, G has a perfect matching iff|N(S)| # |S| for all subsets S " L.Pf. $ This was the previous observation.Marriage Theorem1351'3'5'242'4'LRNo perfect matching:S = { 2, 4, 5 }N(S) = { 2', 5' }.12Pf. ' Suppose G does not have a perfect matching.! Formulate as a max flow problem and let (A, B) be min cut in G'.! By max-flow min-cut, cap(A, B) < | L |.! Define LA = L ( A, LB = L ( B , RA = R ( A.! cap(A, B) = | LB | + | RA |.! Since min cut can't use % edges: N(LA) " RA.! |N(LA )| & | RA | = cap(A, B) - | LB | < | L | - | LB | = | LA |.! Choose S = LA . !Proof of Marriage TheoremLA = {2, 4, 5}LB = {1, 3}RA = {2', 5'}N(LA) = {2', 5'}s1351'3'5't244'1%2'111A%G'%13Which max flow algorithm to use for bipartite matching?! Generic augmenting path: O(m val(f*) ) = O(mn).! Capacity scaling: O(m2 log C ) = O(m2).! Shortest augmenting path: O(m n1/2).Non-bipartite matching.! Structure of non-bipartite graphs is more complicated, butwell-understood. [Tutte-Berge, Edmonds-Galai]! Blossom algorithm: O(n4). [Edmonds 1965]! Best known: O(m n1/2). [Micali-Vazirani 1980]Bipartite Matching: Running Time7.6 Disjoint Paths15Disjoint path problem. Given a digraph G = (V, E) and two nodes s andt, find the max number of edge-disjoint s-t paths.Def. Two paths are edge-disjoint if they have no edge in common.Ex: communication networks.s234Edge Disjoint Paths567t16Disjoint path problem. Given a digraph G = (V, E) and two nodes s andt, find the max number of edge-disjoint s-t paths.Def. Two paths are edge-disjoint if they have no edge in common.Ex: communication networks.s234Edge Disjoint Paths567t17Max flow formulation: assign unit capacity to every edge.Theorem. Max number edge-disjoint s-t paths equals max flow value.Pf. &! Suppose there are k edge-disjoint paths P1, . . . , Pk.! Set f(e) = 1 if e participates in some path Pi ; else set f(e) = 0.! Since paths are edge-disjoint, f is a flow of value k. !Edge Disjoint Pathss t1111111111111118Max flow formulation: assign unit capacity to every edge.Theorem. Max number edge-disjoint s-t paths equals max flow value.Pf. #! Suppose max flow value is k.! Integrality theorem $ there exists 0-1 flow f of value k.! Consider edge (s, u) with f(s, u) = 1.– by conservation, there exists an edge (u, v) with f(u, v) = 1– continue until reach t, always choosing a new edge! Produces k (not necessarily simple) edge-disjoint paths. !Edge Disjoint Pathss t11111111111111can eliminate cycles to get simple paths if desired19Network connectivity. Given a digraph G = (V, E) and two nodes s andt, find min number of edges whose removal disconnects t from s.Def. A set of edges F " E disconnects t from s if all s-t paths uses atleast on edge in F.Network Connectivitys234567t20Edge Disjoint Paths and Network ConnectivityTheorem. [Menger 1927] The max number of edge-disjoint s-t paths isequal to the min number of edges whose removal disconnects t from s.Pf. &! Suppose the removal of F " E disconnects t from s, and |F| = k.! All s-t paths use at least one edge of F. Hence, the number of edge-disjoint paths is at most k. !s234567ts234567t21Disjoint Paths and Network ConnectivityTheorem. [Menger 1927] The max number of edge-disjoint s-t paths isequal to the min number of edges whose removal disconnects t from s.Pf. #! Suppose max number of edge-disjoint paths is k.! Then max flow value is k.! Max-flow min-cut $ cut (A, B) of capacity k.! Let F be set of edges going from A to B.! |F| = k and disconnects t from s. !s234567ts234567tA7.7 Extensions to Max Flow23Circulation with DemandsCirculation with demands.! Directed graph G = (V, E).! Edge capacities c(e), e ) E.! Node supply and demands d(v), v ) V.Def. A circulation is a function that satisfies:! For each e ) E: 0 & f(e) & c(e) (capacity)! For each v ) V: (conservation)Circulation problem: given (V, E, c, d),