• 作者： 譚健民; 蘇文謙
• 作者服務機構： 交通大學資訊科學系
• 中文摘要： 穩定配對問題是將n個男人n個女人，一對一配對，且不能有任何一男一女沒有被配在一起，但他們彼此喜歡對方而比較不喜歡他們所配的夥伴。這種配對方式稱為穩定配對。 由參考文獻（Gale and Shapley, 1962）知，穩定配對一定存在。而在參考文獻（Knuth, 1976），Knuth提出12個相關的研究問題，其中的一個問題如下︰在穩定配對的離合圖中，是否能經由一連串的不穩定夥伴交換而把任一配對方式調整成一個穩定配對。 在這篇論文中，針對上述Knuth所提之問題，我們的答案是否定的，並給予一個最小的反例（含4男4女）。而且我們證明了即使不能把任一配對調整成穩定配對，但總是可以調整成某種更廣義的穩定狀態（穩定分割）。同時，我們給了一些相關的結果。
• 英文摘要： The stable marriage problem is that of matching two disjoint sets of equal size, the men and thewomen, in such a manner that no man and woman who are not partners both prefer each other to theiractual partners under the matching. Such a matching is called a stable matching. One open questionraised by Knuth concerning the divorce digraph of the stable marriage problem is whether any matchingcan be transformed into a stable matching by a sequence of partner interchanges arising from blockingpairs．In this paper, we answer this in the negative and give a smallest counter example containing 4men and 4 women. We show that, although it may not be possible to reach a stable matching, it is alwayspossible to transform an arbitrary matching into a certain generalized stable status. Some related resultsare presented.
• 中文關鍵字： stable marriage problem; stable matching; divorce digraph
• 英文關鍵字： --