程序代写代做代考 CSC373H Lecture 8

CSC373H Lecture 8
Dan Zingaro
November 7, 2016

Maximum Bipartite Matching
􏹩 GivenundirectedgraphG=(V,E),amatchingisasubsetof edges M such that, for each vertex v, v is the endpoint of at most one edge in M
􏹩 v ismatchedbyM ifv istheendpointofsomeedgeinM
􏹩 A maximum matching is matching of maximum cardinality
􏹩 We focus on bipartite graphs
􏹩 Vertex set V can be partitioned into L ∪ R, where all edges in E go between L and R
􏹩 We further assume that every vertex is the endpoint of at least one edge

Bipartite Matching: Example
Here is a bipartite graph. Find a matching of 2 edges. Find a (maximal) matching of 3 edges.

Reducing to Maximum Flow
􏹩 We can try to solve the maximum-matching problem from scratch — there are good ways to do so
􏹩 But, maximum-flow is a general technique that can be used to solve many problems, including maximum-matching
􏹩 In particular, if we can reduce the maximum-matching problem to max-flow, then all we do is run max-flow to solve the problem
􏹩 What does it mean to reduce to max-flow?

Reducing to Maximum Flow…
􏹩 The goal is to create a flow network G′ so that matchings in G correspond to flows in G′
􏹩 We want that G has a matching M with |M| edges iff G′ has a flow with value |M|
􏹩 ThenallwedotofindamaximummatchinginG isfinda maximum flow in G′
􏹩 . . . and we already know how to find a maximum flow!

Reducing to Maximum Flow…
Here’s how we can construct flow network G′ from bipartite graph G:
􏹩 Add new source vertex s and sink vertex t to G′, along with all original vertices
􏹩 ForeachundirectededgeinGfromu∈Ltov∈R,add directed edge (u,v) to G′
􏹩 Also add to G′ edges from s to each vertex in L, and from each vertex in R to t
􏹩 (G′ has 2 more vertices and |V| more edges than G)
􏹩 Finally, give each edge in G′ a capacity of 1

Reducing to Maximum Flow: Example
Here’s the flow network for our earlier bipartite graph.

Proof of Reduction
􏹩 LetG=(V,E)beabipartitegraphwithvertexpartition V=L∪R
􏹩 Let G′ = (V′,E′) be its corresponding flow network
􏹩 Call flow f integer-valued if it assigns integer flow to each
edge in E′
􏹩 We will now prove the “if” and “only if” parts of the correspondence between matchings and flows

Proof of Reduction…
Part 1:
If M is a matching in G, then there is an integer-valued flow f in G′ withvalue|f|=|M|.
􏹩 We’re given a matching with |M| edges, and we have to find a flow with value |M|
􏹩 Here’s a flow that does that
􏹩 If(u,v)∈M,thenf(s,u)=f(u,v)=f(v,t)=1
􏹩 For all other edges e, f(e) is 0
􏹩 Capacity and conservation constraints are satisfied
􏹩 Andforeach(u,v)∈M,1unitofflowleavess,so|f|=|M|

Proof of Reduction…
Part 2:
If f is an integer-valued flow in G′, then there is a matching M in G with |M| = |f |.
􏹩 We’re given a flow with value |f |, and we have to find a matching with |f | edges
􏹩 Here’s a matching that does that
􏹩 LetMbetheedges(u,v)whereu∈L,v∈R,andf(u,v)=1
􏹩 We have to prove three things about M
􏹩 Exactly one edge leaves each vertex u
􏹩 Exactly one edge enters each vertex v
􏹩 M actually has |f | edges!

Proof of Reduction…
Does exactly one edge leave u?
􏹩 u has exactly one incoming edge, from s, and its capacity is 1 􏹩 That 1 unit of flow leaves u on edge (u,v)
􏹩 So, no more flow can leave u on any other edge
􏹩 Therefore, there can be only one edge for which u is the tail

Proof of Reduction…
Does exactly one edge enter v?
􏹩 v has exactly one outgoing edge, to t, and its capacity is 1
􏹩 That 1 unit of flow enters v on edge (u,v)
􏹩 So, no more flow can enter v on any other edge
􏹩 Therefore, there can be only one edge for which v is the head

Proof of Reduction…
Does M have |f | edges?
􏹩 Considercut(A,B)inG′,whereA={s}∪Land
B = {t} ∪ R
􏹩 No edges enter A, so |f | is the total flow leaving A 􏹩 M consists of all edges carrying flow from A
􏹩 Each of these edges in M carries 1 flow, so there must be |f | of them

Edge-Disjoint Paths
􏹩 A set of paths is edge-disjoint if no two paths in the set share an edge
􏹩 The paths can share vertices
􏹩 GivendirectedgraphG=(V,E)withdistinguishedverticesa and b, the goal is to find the maximum number of edge-disjoint paths that go from a to b

Edge-Disjoint Paths: Example
v0
v1
v4
v5
v2
v3
v6
v7
What is the maximum number of edge-disjoint paths from v0 to v7? v2 to v6?

Edge-Disjoint Paths: Reduction
􏹩 We can reduce this problem to max-flow
􏹩 Define flow network G′ to have the same nodes and edges as
G, with s = a and t = b
􏹩 Set the capacity of each edge to 1
􏹩 Now, the required proof is that there are k edge-disjoint paths inG iffthereisaflowofvaluek inG′

Edge-Disjoint Paths: Proof
Part 1:
􏹩 We must show that if there are k edge-disjoint paths from a to b in G, then there is a flow of value k in G′
􏹩 Consider the flow in G′ with
􏹩 f(e)=1foreachedgeethatisonanyofthepaths
􏹩 f(e′)=0foranyedgee′ thatisnotonanyofthepaths
􏹩 The flow has value k, as required

Edge-Disjoint Paths: Proof…
Part 2:
􏹩 Ifthereisaflowf ofvaluek inG′,thentherearek
edge-disjoint paths from a to b in G
􏹩 For any flow network with integer edge capacities, there is an
integer-valued flow of maximum value (prove this!)
􏹩 As edge capacities are all 1, Each edge that carries flow must carry exactly 1 unit of flow
􏹩 Sowecaninsteadthinkaboutinteger-valued,0-1flows…

Edge-Disjoint Paths: Proof…
ifthereisa0-1flowf ofvaluek inG′,thenthesetofedges carrying flow constitutes k edge-disjoint paths in G
􏹩 The proof is by induction on the number of edges in f that carry flow
􏹩 If there are 0 such edges, then |f | = 0. Nothing to prove
􏹩 Otherwise, at least one edge carries flow. Therefore, there
must be an edge (s,u) that carries one unit of flow.
􏹩 As u has 1 unit of flow entering, it must have 1 unit of flow
leaving on some edge (u,v)
􏹩 But now v has 1 unit of flow entering, so it must have 1 unit
of flow leaving on edge (v, w)
􏹩 We continue this process until one of two things happens: we reach t or we form a cycle

Edge-Disjoint Paths: Proof…
1. We reach t
􏹩 We use the s → t path as 1 of the k required edge-disjoint
paths
􏹩 Let f ′ be the flow obtained by decreasing the flow on the edges of this path to 0
􏹩 |f′|=k−1,andithasfeweredgesthanf thatcarryflow
􏹩 Applyingtheinductivehypothesistof′,wegetk−1
edge-disjoint paths
􏹩 Adding the edge-disjoint path that we found, we have k disjoint paths, as required

Edge-Disjoint Paths: Proof…
2. We reach a node n that we have reached before
􏹩 Consider the cycle of edges visited between the first and
second visit of n
􏹩 Obtain flow f ′ from f by decreasing the flow of each edge on
this cycle to 0
􏹩 This doesn’t change the flow value, but does decrease the number of edges that carry flow
􏹩 By the inductive hypothesis, we get k edge-disjoint paths from f ′, as required