Bipartite Graph and Stable Marriage Problem

Bipartite graph 的定義，是一個 graph 中的所有 nodes，依據問題的性質分為兩類型的 disjoint set（即任一個 node 不可以同時出現在此二類 sets），並且 edges 只建立於此二 set 彼此間，而同一 set 中的 node 不會建立 edges。

以一個不太好的例子來說明。假定 bipartite graph 的兩類 nodes 為 human 與 event，edge 在某人參與此 event 時，會被建立。在此，human 包含男人與女人，event 則為 like（不同形式的喜歡，或好感），一個男人或女人可能同時喜歡多個異性（這是不好的..），那麼這個 graph 可表示如下圖左方（矩形代表喜歡或好感，圓形代表 human）。這樣的表示方式看起來似乎男女之間彼此沒有 edge 存在，但其實他們彼此的複雜關係是呈現在 event 的，如果我們將左邊的 bipartite graph 轉為右邊的 graph，男女的關係就顯而易見了。右邊 graph 的 edge 是在男女雙方相互喜歡時，才被建立。

其實，若要以 bipartite graph 來描述男女配對關係，比較合適的表示方式為，graph 的一邊是男人，另一邊是女人，每個男人或女人會有一個自己對於異性的喜歡程度列表（preference order list）（假定一般情況下，異性互相喜歡），因此 set 之內不會有連結，之間有連結。這種表示方式即為著名的穩定婚姻問題（Stable Marriage Problem，SMP）。SMP 問題的定義是，在上述的男女表示方式下，如何達到穩定（stable）也就是如何兼顧使得最多人能被配對到，並且都對配對的對方能有較高的喜歡程度（即在 preference order list 中排名較前面）。如下圖，右圖就是達到最大配對的結果。通常這種問題被轉為 Maximum-flow problem，並以 Ford-Fulkerson Algorithm 解之。