Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne7. Network Flow ApplicationsAlgorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne7.6 Disjoint Paths3Disjoint 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 Paths567t4Disjoint 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 Paths567t5Max 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 t111111111111116Max 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 t111111111111117Network 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 Connectivitys234567t8Edge Disjoint Paths and Network ConnectivityMenger's Theorem (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. !s234567ts234567t9Disjoint Paths and Network ConnectivityMenger's Theorem (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. !s234567ts234567tAAlgorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne7.5 Bipartite Matching11Matching.! 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.Matching12Bipartite 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'RL13Bipartite 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'14Max 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'15Theorem. 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'G16Theorem. 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'17Def. 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 Matching18Notation. 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'LR19Marriage 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' }.20Pf. ' 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'&21k-Regular Bipartite GraphsDancing problem.! Exclusive Ivy league party attended by n men and n women.! Each man knows exactly k women; each woman knows exactly k men.! Acquaintances are mutual.! Is it possible to arrange a dance so that each woman danceswith a different man that she knows?Mathematical reformulation. Does every k-regularbipartite graph have a perfect matching?Ex. Boolean hypercube.1351'3'5'242'4'womenmen22Theorem. [König 1916, Frobenius 1917] Every k-regular bipartite graphhas a perfect matching.Pf. Size of max matching = value of max flow in G'.
View Full Document
Unlocking...