【正文】 ion 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。E) has a perfect matching if and only if |N(S)| = |S| for every subset S of V and for every subset S of W. This is a deep theorem. It characterizes exactly when a bipartite graph does not have a perfect matching. (Now you can convince the king.) Is it the only situation when a bipartite graph does not have a perfect matching? Hall said yes in 1935. This Lecture ? Problem and Hall’s theorem ? Reductions and Applications ? Proof of Hall’s theorem (optional) Application 1: Job Assignment Hackson Marking Jesse Tom Leo Tutorials Solutions Newsgroup Job Assignment Problem: There are n persons and n jobs. Each person is willing to do a subset of jobs. Can you find an assignment so that all jobs are taken care of while everyone is responsible for at most one job? A perfect matching corresponds to a perfect assignment. Job Assignment Problem: There are n persons and n jobs. Each person is willing to do a subset of jobs. Can you find an assignment so that all jobs are taken care of while everyone is responsible for at most one job? In fact, there is an efficient algorithm to find such as assignment! (CSC 3160) We can model the job assignment problem as a bipartite matching problem. We create a vertex for each person, and we create a vertex for each job. If a person is willing to do a job, then we add an edge between them. Then a perfect matching corresponds to a perfect “assignment”. This problem can be generalized to give different workload to each person. Application 1: Job Assignment Application 2: Domino Puzzle Can you fill a (inplete) chessboard perfectly with dominos? Application 2: Domino Puzzle Create a vertex for each square in the board. Add an edge for two squares if they are adjacent. This is a bipartite graph with the black and white squares form the two sides. A perfect matching in this graph corresponds to a perfect placement of dominos. Application 2: Domino Puzzle This is another example where we can model a problem as a graph problem. App