Suppose we are playing in the universal studio, and we want to take the roller coaster. Each row only has two seats, and one female has to sit with a male. Everyone wants to sit with someone he/she knows. For example, if female 1 knows male 1, they can sit together. Those who know each other are female 1 (f1), male 1 (m1), (f1, m2), (f2, m2, m3), (f3, m1).
This kind of graph is called bipartite graph. The definition is: if the nodes in a graph can be divided into two groups, X and Y, and all the edges link one node in X and one node in Y. In other words, no edge link two nodes in X or Y.
We want to find the combination such that the total number of match is maximum.Start with f1. If she sits with m1, then f2 can sit with m2. However, f3 can only sit with m1, but m1 is sitting with f1.
To solve this problem, f3 asks m1 whether they can sit together. As a result, m1 asks f1 whether she can sit with other guys she knows. f1 then goes to m2, ans asks to sit together. m2 says: let me ask f2 whether she can find someone else. Eventually, f2 comes to m3, and since no one sits with him, they can sit together. Consequently, m2 can sit with f1, and m1 can sit with f3.
No comments:
Post a Comment