bipartitematching-文庫吧在線文庫
【正文】 ith numbers from 1 to n so that: ? Each row contains every number from 1 to n. ? Each column contains every number from 1 to n. Suppose you are given a partial Latin Square when some rows are already filled in. Can you always extend it to a Latin Square? Using bipartite matching, we can prove that the answer is yes. Application 3: Partial Latin Square The proof consists of two steps: (1) Reduce the problem into a bipartite matching problem. (2)Prove that the bipartite matching problem always has a solution by Hall’s theorem. Step 1: Reduction to Bipartite Matching Given a partial Latin square, we construct a bipartite graph to fill in the next row. column number 1 2 3 4 5 1 2 3 4 5 Create one vertex for each column, and one vertex for each number. Add an edge between column i and color j if color j can be put in column i. We want to “match” the numbers to the columns. First, we reduce the problem to a bipartite matching problem. Given a partial Latin square, we construct a bipartite graph to fill in the next row. A perfect matching corresponds to a valid assignment of the next row. column number 1 2 3 4 5 1 2 3 4 5 1 5 2 4 3 If we can always plete the next row, then by induction we are done. The key is to prove that the bipartite graph always has a perfect matching. Step 1: Reduction to Bipartite Matching Using Hall’s Theorem A graph is kregular if every vertex is of degree k. A 3regular bipartite graph Hall’s Theorem: A bipartite graph G=(V,W。E) has a perfect matching if and only if |N(S)| = |S| for every subset S of V. Hall’s Theorem: If |N(S)| = |S| for every subset S of V, then there is a perfect matching. Proof of Hall’s Theorem Case 1: Every proper subset S has |N(S)| |S|. (Easy case) 1. Just delete an edge. 2. By deleting an edge, |N(S)| can decrease by at most 1. 3. Since |N(S)| |S| before, 4. we still have |N(S)| = |S| after deleting an edge. 5. Since the graph is smaller (one fewer edge), by induction, 6. there is a perfect matching in this smaller graph, 7. hence there is a perfect matching in the original graph. Hall’s Theorem: If |N(S)| = |S| for every subset S of V, then there is a perfect matching. Proof of Hall’s Theorem Case 2: Suppose there is a proper subset S with |N(S)| = |S|. S N(S) Divide the graph into two smaller graphs G1 and G2 (so we can apply induction
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1