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 3Matching, maximum matching ◼ Matching: a collection of vertex￾disjoint 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