史灵生《离散数学》清华大学-D10Matching.pdfVIP

Discrete Mathematics Lecture 10 Matching in Graphs 1 10.1-2 A Dancing Problem A graph is bipartite if its nodes can be partitioned into two classes, say A and B, such that every edge connects a node in A to a node in B. 2 10.1-2 A Dancing Problem A matching is a set of edges that have no endpoint in common. A matching is perfect if it covers all nodes. 3 Theorem 10.1.1 (König’s Theorem) Every bipartite d-regular graph with d0 contains a perfect matching. Def. Given a graph G=(V, E) and v∈V, the set of neighbors of v is denoted by N(v). Let S ⊂V, define the set of neighbors of S by N (S ) : N (v). vS 4 10.3 The Main Theorem Theorem 10.3.1 (The Marriage Theorem) A bipartite graph has a perfect matching iff |A |=|B | and for any subset S ⊂A , |S | ≤ |N(S)|. Note. If we interchange “A ” and “B”, perfect matchings remain perfect matchings. But what happens to the condition stated in the theorem? 5 It remains valid. Let T⊂B. Then |A |-|N(T)| = |A\N(T)| ≤ |B\T| = |B |-|T|, ⇒|T| ≤ |N(T)|. N(T) T A B 6 Proof of The Marriage Theorem. Use induction on the number of nodes of the bipartite graph. a b R A