Concrete and simple applications for bipartite graphs

Problem Detail: 

I am looking for concrete and simple problems that may be solved using bipartite graphs or bipartite graph properties. Any idea along with explanations are welcome.

Asked By : Laurent

Answered By : John Bupit

Assignment Problem would be one such example:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.

Hall's Marriage Theorem would be another:

Imagine two groups; one of n men, and one of n women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.

The Mutilated Chessboard Problem can be solved using The Hall's Theorem:

Suppose a standard 8x8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2x1 so as to cover all of these squares?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24057