Minimum Cut ProblemSlide 2Edge Disjoint PathsSlide 4Slide 5Slide 6Network ConnectivityEdge Disjoint Paths and Network ConnectivityDisjoint Paths and Network ConnectivityThere are 3 arc-disjoint s-t pathsDeleting 3 arcs disconnects s and tNode disjoint pathsPowerPoint PresentationThere are 2 node disjoint s-t paths.Deleting 5 and 6 disconnects t from s.7.5 Bipartite MatchingBipartite MatchingApplicationMatchingSlide 20Slide 21MatchingsTransformation to a Max Flow ProblemFind a max flowSlide 25Bipartite Matching: Proof of CorrectnessSlide 27Graph Connectivity and Minimum CutsSlide 29Slide 30Slide 31DefinitionsSlide 33ExercisesSlide 35Slide 36Slide 37Flow network.Abstraction for material flowing through the edges.G = (V, E) = directed graph, no parallel edges.Two distinguished nodes: s = source, t = sink.c(e) = capacity of edge e.Minimum Cut Problems234567t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4capacitysourcesinkMin s-t cut problem. Find an s-t cut of minimum capacity.Minimum Cut Problems234567t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 A Capacity = 10 + 8 + 10 = 283Disjoint path problem. Given a digraph G = (V, E) and two nodes s and t, 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 and t, 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 edgeProduces k (not necessarily simple) edge-disjoint paths. ▪Edge Disjoint Pathss t11111111111111can eliminate cycles to get simple paths if desired7Network connectivity. Given a digraph G = (V, E) and two nodes s and t, 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 at least on edge in F.Network Connectivitys234567t8Edge Disjoint Paths and Network ConnectivityTheorem. [Menger 1927] The max number of edge-disjoint s-t paths is equal 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 ConnectivityTheorem. [Menger 1927] The max number of edge-disjoint s-t paths is equal 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. ▪s234567ts234567tAThere are 3 arc-disjoint s-t pathsst123456789101112Deleting 3 arcs disconnects s and t•Let S = {s, 3, 4, 8}. The only arcs from S to T = N\S are the 3 deleted arcs.t125679101112s34 8Node disjoint paths•Two s-t paths P and P' are said to be node-disjoint if 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 splitting•Theorem. 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 in N\{s,t} whose removal from G disconnects all paths from nodes s to node t.Thm 6.8) (Menger’s Thm)maximum number of node disjoint s-t paths = minimum number of s-t vertex cut.Pf) Construct G’ using node splittingnode i in G → node i’, i’’, and arc (i’, i’’) with capacity 1(except s, t)incoming arcs to node i → incoming arcs to i’ outgoing arcs from node i → outgoing arcs from i’’ (i, j)A → set capacity of original arcs at Flow of v units in G’ gives v arc disjoint paths andv arc disjoint paths in G’ v node disjoint paths in GAlso any finite capacity s-t cut in G’ has only node-splitting arcsTherefore, any s-t cut in G’ with capacity k corresponds to a set of k nodes whose removal from G destroys all paths from node s to node t.By max-flow min-cut theorem, max number of node-disjoint s-t paths in G = minimum number of s-t vertex cut in G. For undirected network, can replace each edge by two directed arcs with opposite direction. Then the results still hold for undirected case.Network Theory and Applications 201013There are 2 node disjoint s-t paths.st123456789101112Deleting 5 and 6 disconnects t from s.•Let S = {s, 1, 2, 3, 4, 8}•Let T = {7, 9, 10, 11, 12, t}•There is no arc directed from S to T.t7910111256s1234 87.5 Bipartite MatchingBipartite Matching•A graph G=(V,E) is bipartite if the vertices can be partitioned into disjoints sets X,Y•A matching M is a subset of the edges that does not share any vertices•Find a matching as large as possibleApplication•A collection of teachers•A collection of courses•And a graph showing which teachers can teach which coursesRAPBCCDGAK30332132640142119Matching.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.Matching20Bipartite 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' RL21Bipartite 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'
View Full Document
Unlocking...