穩定配對的離合問題

Abstract

自從1962年,Gale and shapley 提出穩定配對問題以來，此問題一直是電腦科學、數 學界、經濟領域裡的一個主要研究課題。且至今已有九百篇有關穩定配對問題的論文 發表，甚至出版了書籍，如Irving所著"The Stable Marriage Problem:Structure a nd Algorithms"等等。 穩定配對問題是將n 個男人n 個女人, 一對一配對, 且不能有任合一男一女沒有被配 在一起但他們彼此喜歡對方而比較不喜歡他們所配的夥伴。這種配對方式稱為穩定配 對。 對於任一穩定配對問題，穩定配對一定存在。而在1976年, Knuth 提出12個相關的研 究問題，其中的一個問題如下：在穩定配對的離合圖中，是否能經由一連串的不穩定 夥伴交換而把任一配對方式調整成一個穩定配對。 在這篇論文中，針對上述Knuth 所提之問題，我們的答案是否定的，并提出下列幾個 相關結果： (1) 給予一個最小的反例(含4男4 女); (2) 我們提出了一個演算法且證明了即使不能把任一配對調整成穩定配對但總是可以 調整成某種更廣義的穩定狀態( 穩定分割)。 (3) 根據我們的演算法, 可以產生一系列的反例( 在其相對的離合圖中, 存在某些配 對不能被調整成一個穩定配對)。