介绍稳定匹配
一、穩定匹配的定義
1、穩定分配方案
這里以碩士研究生與導師之間的雙向選擇為例來說明穩定匹配問題。
假設師生分配問題中一個老師可以帶三個學生，而一個學生只能跟一個導師。這里我們可能提前聯系的導師有好幾個，可能答應了某個導師后又反悔，導師也可能被很多學生選擇，所以這里就涉及到一個分配問題。
若最后的分配方案能保證：
（1）如果有學生想要換導師，那么沒有教師愿意接受這名學生。
（2）如果有教師想要換學生，那么沒有學生愿意跟隨這位教師。
那么就稱此師生分配方案是穩定的。
我們可以對上述穩定分配方案的定義做進一步形式化的處理，假設學生對于想選的教師會有一個優先排名，而教師對于想要招的學生也會有一個優先排名。
如果對每一個教師P和每一個沒有跟隨教師P的學生S，至少出現下列兩種情形之一:
（1）教師P對他已經接受的每位學生都比對學生S更滿意;
（2）學生S對他目前的導師比對教師P更滿意。
則稱此方案為穩定分配方案。
2、不穩定分配方案
如果至少存在一個教師P和一個沒有跟隨教師P的學生S,使得以下兩點均滿足:
（1）教師P對學生s至少比他所接受的學生中的一位更滿意;
（2）學生S對教師P比對他目前的導師更滿意。
那么就說明師生分配方案是不穩定的。
二、穩定匹配的求解
1、G-S算法說明
這里引入G-S算法。
求解穩定的師生分配方案的G-S算法敘述如下:
每次只選擇一位學生S，讓他(她)按照自己的優先表從高到低依次找還沒有面談過的教師面談。為公平起見，我們假設這位學生是通過完全隨機的方式選出來的。如果與他(她)面談的教師目前沒有候選的學生，那么這位教師最安全的做法就是把這位學生列為候選學生，即使這個學生未必是這位老師的優先表中靠前的學生，因為每位教師必須要帶一名學生。如果這名教師已經有了候選學生S’,那么他將應該比較學生S和學生S’ ,并從中挑選一個作為他的候選學生。按照這一程序,學生S必然在這一輪面談后被某個教師考慮為候選學生。
然后,再隨機選擇一位自由的(即還沒有成為候選對象的)學生，讓他(她)按照自己的優先表從高到低依次找自己還沒有面談過的教師面談，直到成為候選學生。這一迭代過程一直進行下去，直到所有學生都成為候選學生或每一個自由的學生都與所有教師面談過為止。
在研究上述算法性質時，首先要注意到，盡管只有N個學生，該算法一般說來未必在N步之后就終止。這是因為，已經成為候選學生的人有可能在后面的某次迭代中被另一位同學頂替掉而再次成為完全自由的學生。因此，針對該算法我們依次需要考察如下問題：該算法是否會終止？如果會，迭代多少步之后終止？該算法是否能夠得到一個完全匹配?如果能，這個完全匹配是否一定為穩定匹配？在回答這些問題之前，首先注意到算法的幾個似乎是讓學生越來越沮喪,教師越來越高興的基本事實:
（1）教師P從第一次有學生去和他面談開始,就一直會有候選學生，而且他的候選學生只會越變越好(按照教師P的優先表);
（2）學生S可能會在候選學生和自由學生狀態之間交替，而且他(她)去面談的教師只會越變越差(按照學生S的優先表)。
（3）如果學生S在算法的某一步是自由的,那么此時，必至少存在一位該學生沒有面談過的教師。
事實三意味著算法終止的唯一條件為所有的學生都是候選學生，即找不到自由的學生。
2、G-S算法定理
定理1： G-S算法在至多 N2^22次迭代之后終止，且算法終止時所得到的集合是一個完全匹配。
定理2： G-S算法終止時所得到的集合Ω\OmegaΩ一定是一個穩定匹配。
定理3： G-S算法所有執行得到的都是對學生最滿意、對教師最不理想的穩定匹配。
定理4 一個左右節點數相同的二分圖存在完全匹配的充要條件是它不包含抑制集。
三、穩定匹配的公平性
（1）從學生角度看，將導致學生之間的公平性問題：在算法執行過程中，是否早被選上的學生更有利？
（2）因為算法的兩個基本事實是學生越來越沮喪，教師越來越高興，那么會導致學生與教師之間的公平性問題：該算法總體上知否對教師更有利？
對于第一個公平性問題，學生完全不必擔心：算法的每次執行得到的都是同一個集合n。對于第二個公平性問題，學生更加不必擔心：這一算法得到的結果是對學生最有利的。
由此也得出了定理3。
四、完全匹配存在的條件
上述師生分配問題有一個前提就是每一個學生與每一個教師都有配對的可能性。但如果教師只愿意接受某幾個學生，學生也只愿意跟隨某幾個導師，這種情況下就可能不存在完全匹配。
所以完全匹配是存在一定條件的。
假設有5個教師和5個學生，他們的意愿用上圖左邊的圖表示。例如，教師1只愿意在學生1和學生2中做選擇。此時,我們很容易發現并不存在完全匹配：學生1、學生2和學生3這3個學生只愿意在教師1和教師2這兩個教師之間做選擇。我們稱學生1、學生2和學生3這了個學生的集合為一個抑制集，因為他們與二分圖另一端的連接抑制了完全匹配的形成。
一般地，對于二分圖右端的一組節點S，如果左端某個節點有邊與S中的某個節點連接，我們就稱該節點為S的鄰居節點。S的所有鄰居節點的集合記為N(S)。如果S中的節點數目嚴格大于N(S)中的節點數目,則右端的節點集合S是抑制的。
顯然，只要一個二分圖中存在抑制集，那么就不存在完全匹配。現在的問題是:還有哪些其他因素導致不存在完全匹配?是否會存在很多這樣的因素?定理4表明，存在抑制集是不存在完全匹配的唯一理由。
總結
