CSC3160: Design and Analysis of Algorithms Week 10: Stable Matching and Secretary Problem Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Bipartite graph (Undirected)Bipartite graph: G=(V,E)for which V can be partitioned into two parts oV=MUW with M∩W=④， And all edges e =(m,w) have m∈and w∈W. M W 2
Bipartite graph ◼ (Undirected) Bipartite graph: ◼ 𝐺 = (𝑉, 𝐸) for which 𝑉 can be partitioned into two parts ❑ 𝑉 = 𝑀 ∪ 𝑊 with 𝑀 ∩ 𝑊 = ∅, ◼ And all edges 𝑒 = 𝑚, 𝑤 have 𝑚 ∈ 𝑀 and 𝑤 ∈ 𝑊. 𝑀 𝑊 2
Matching,maximum matching Matching:a collection of vertex- disjoint edges 0 a subset E'E s.t.no two edges e,e'∈E'are incident. E':size of matching. Maximum matching:a matching with the maximum size. M W This lecture:matching in a bipartite graph 3
Matching, maximum matching ◼ Matching: a collection of vertexdisjoint edges ❑ a subset 𝐸′ ⊆ 𝐸 s.t. no two edges 𝑒, 𝑒 ′ ∈ 𝐸 ′ are incident. ◼ |𝐸′|: size of matching. ◼ Maximum matching: a matching with the maximum size. ◼ This lecture: matching in a bipartite graph 𝑀 𝑊 3
Perfect matching There may be some vertices not incident to any edge. Perfect matching:a matching with no such isolated vertex. ▣needs at least:|M=lW M W We'll assume M=W in the rest of the lecture. 4
Perfect matching ◼ There may be some vertices not incident to any edge. ◼ Perfect matching: a matching with no such isolated vertex. ❑ needs at least: |𝑀| = |𝑊| ◼ We’ll assume |𝑀| = |𝑊| in the rest of the lecture. 𝑀 𝑊 4
Men's Preference Suppose a man sees these women. He has a preference among them. What's your preference list? Different men may have different lists. 5
Men’s Preference ◼ Suppose a man sees these women. ◼ He has a preference among them. ❑ What’s your preference list? ◼ Different men may have different lists. 5