Bipartite Graph

Intro

the assignment of graduating medical students to their first hospital appointments.[1] In 2012, the Nobel Prize in Economics was awarded to Lloyd S. Shapley and Alvin E. Roth "for the theory of stable allocations and the practice of market design."

Useful Theorems

Check a graph is bipartable

DFS

BFS

Color Method

Reading

http://www.math.caltech.edu/~2014-15/2term/ma006b/02 bipartite.pdf https://en.wikipedia.org/wiki/Stable_marriage_problem