bipartitematching-全文預(yù)覽
【正文】 e, it is important to learn 1. how to use bipartite matching to solve problems, and 2. how to apply Hall’s theorem. The proof of Hall’s theorem is optional. 。E) has a perfect matching if and only if |N(S)| = |S| for every subset S of V and W. Step 2: Completing Latin Square Claim: Every kregular bipartite graph has a perfect matching. column number 1 2 3 4 5 1 2 3 4 5 The bipartite graphs ing from Latin square are always regular because: Suppose there are k unfilled rows. Then each column has nk distinct numbers, and so connected to k numbers. Each number appeared in nk columns above, and so connected to k columns. So, the bipartite graph is kregular, and thus always has a perfect matching. More Applications (Optional) The bipartite matching problem is an important problem and has many applications. One important application is the “maximum flow problem”. This is to find the maximum number of “edge disjoint paths” between two nodes. This can be applied to find the maximum amount of information one can send from one point in the work to another point in the work. This problem can be reduced to the bipartite matching problem (CSC 3160). This Lecture ? Problem and Hall’s theorem ? Reductions and Applications ? Proof of Hall’s theorem (optional) Proof of Hall’s Theorem (easy direction) One direction is easy, if there is a perfect matching, then |N(S)| = |S| for every subset S of V. S N(S) Just consider the neighbours of S in the perfect matching. Hall’s Theorem: A bipartite graph G=(V,W。Bipartite Matching Lecture 8: Oct 7 This Lecture Graph matching is an important problem in graph theory. It has many applications and is the basis of more advanced problems. In the last lecture we consider the stable matching problem. Today we will study the bipartite matching problem. ? Problem and Hall’s theorem ? Reductions and Applications ? Proof of Hall’s theorem (optional) Bipartite Matching The Bipartite Marriage Problem: ? There are n boys and n girls. ? For each pair, it is either patible or not. Goal: to find the maximum number of patible pairs. Bipartite Matching The Bipartite Marriage Problem: ? There are n boys and n girls. ? For each pair, it is either patible or not. Goal: to find the maximum number of patible pairs. Graph Problem A graph is bipartite if its vertex set can be partitioned int
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1