6.042J Lecture Notes - Lecture 12: Mathematical Induction, If And Only If, Graph Coloring
13 Apr 2016
School
Course
Professor
Document Summary
A bipartite graph is a graph whose vertices can be partitioned into two sets, l(g) and r(g), such that every edges has one endpoint in l(g) and one endpoint in r(g) Matching problem: suppose that we have a set of men and an equal-sized or larger set of women, and these is a graph with an edge between a man and a woman if the man like that woman. A match is de ned to be an assignment of a woman to each man so that different men are assigned to different women and a man is always assigned to a woman that he likes. In this scenario, the likes relationship need not be symmetric. Think of the women as the images of the men. Every subset of men likes at least as large a set of women, |s| |e(s)| Hall"s matching theorem gives necessary and suf cient conditions for the existence of a match in a bipartite graph.
