【正文】 ? 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 into two subsets A and B so that each edge has one endpoint in A and the other endpoint in B. A matching is a subset of edges so that every vertex has degree at most one. A B The bipartite matching problem: Find a matching with the maximum number of edges. Maximum Matching A perfect matching is a matching in which every vertex is matched (. of degree 1). The perfect matching problem: Is there a perfect matching? Once you know how to solve perfect matching, you can also do maximum matching. Examples Which bipartite graphs have a perfect matching? Examples Which bipartite graphs have a perfect matching? Working for the King Suppose you work for the King, and your job is to find a perfect matching between 200 men and 200 women. If there is a perfect matching, then you can show it to the King. But suppose there is no perfect matching, how can you convince the King this fact (. there is really no perfect matching, not because you are inpetent)? One attempt is to try all the possibilities and show that none works, but you can imagine the King won’t have the time and patience for that. Is that a smarter way? It is difficult to argue that no solution exists. Examples Which bipartite graphs have a perfect matching? Some Notation S N(S) Let S be a subset of vertices on one side, and |S| be the number of vertices in S. Let N(S) be the neighbours of vertices in S, . a vertex v belongs to N(S) iff v is a neighbor of some vertex in S. Let |N(S)| be the number of vertices in N(S). A Necessary Condition S N(S) If |N(S)| |S| for some S, then it is impossible to have a perfect matching. In other words, in order to have a perfect matching, a necessary condition is that for all subsets S on one side, we must have |N(S)| = |S|. Hall’s Theorem Hall’s Theorem: A bipartite graph G=(V,W