離散數(shù)學(xué) 課件5.2-最大匹配及穩(wěn)定匹配

第6.2節(jié)最大匹配及穩(wěn)定匹配離散數(shù)學(xué)講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學(xué)，電子工業(yè)出版社，2025最大匹配由上節(jié)，我們知道對于一個二部圖中的匹配M來說,若圖中沒有M增廣路徑,則M就是最大匹配了.這就為我們提供了一種求最大匹配的方法.設(shè)M是(X,Y)-二部圖G中的一個給定的匹配(可以是空集),如果M不是最大匹配,則一定存在一條M增廣路徑,此路徑一定是從未被M浸潤的X中頂點(diǎn)出發(fā)并終止于Y中未被M浸潤的頂點(diǎn)的M交錯路徑.

輸入:

(X,Y)-二部圖.G的一個匹配M,U=X-V(M).

例5.2.1考慮圖(a)中的二部圖.二部圖的一個匹配用粗邊M給出.下面就利用最大匹配算法從此匹配開始尋找一個最大匹配.(a)(b)

(a)(b)(c)(d)

(c)(d)

注5.2.1兩種擴(kuò)展另一種擴(kuò)展是尋找加權(quán)二部圖中的權(quán)值最大的匹配.Kuhn(1955)解決了這個問題(由于K?nig和Egerváry的工作是上述算法的基礎(chǔ),為了紀(jì)念這兩位匈牙利數(shù)學(xué)家,Kuhn把此算法稱為匈牙利算法).注5.2.1兩種擴(kuò)展穩(wěn)定匹配

Gale-Shapley算法:每個男士(女士)按照喜好順序給每個女士(男士)排序.最喜歡的排在第一位,依次排列.每位男士向排在第一位的女士求婚.某個女士若有多個追求者,則該女士與她的排序最前面的男士訂婚.若某個女士只有一個追求者,則訂婚.若所有男士都訂婚,則算法終止.剩下的男士(即還沒有訂婚者)繼續(xù)向排在第二位的女士求婚.每位女士在新求婚者,未婚夫(如果在上一步已訂婚)中尋找排序最前面的男士訂婚.繼續(xù)上面的過程,即還未訂婚的男士向還未追求過的最喜歡的女士求婚.而每位女士在新求婚者,未婚夫(如果已訂婚)中尋找排序最前面的男士訂婚.若每個男士都已訂婚(當(dāng)然同時每位女士也已訂婚)時,算法終止.

注:算法每個階段分二步,一是男士求婚,二是女士選擇;每一階段,都有可能某位女士沒有一人追求,因此也不用做出選擇;女士可以悔婚,也即在上一步已經(jīng)訂婚,下一步若遇到更心儀的追求者,可以和后者訂婚,和上一步的訂婚者悔婚.Gale-Shapley算法例5.2.2假設(shè)有4個男士和4個女士,他們之間的喜好程度由下表給出.現(xiàn)在我們來說明Gale-Shapley算法怎么給出一個穩(wěn)定匹配.

注5.2.2每個穩(wěn)定婚姻問題中存在穩(wěn)定匹配且穩(wěn)定匹配未必唯一.若將Gale-Shapley算法變?yōu)榕壳蠡?則得到的穩(wěn)定匹配和男士求婚的穩(wěn)定匹配未必一樣.且男士或女士求婚的Gale-Shapley算法只能找到所有穩(wěn)定匹配中的兩個.利用Gale-Shapley算法可能得到兩個穩(wěn)定匹配,那么這兩個穩(wěn)定匹配在所有穩(wěn)定匹配中的“地位”怎么樣?或者說這兩個穩(wěn)定匹配和其它穩(wěn)定匹配(如果有的話)的關(guān)系如何?為了回答這個問題,我們先介紹幾個概念.

類似可定義男士最差的穩(wěn)定匹配、女士最優(yōu)穩(wěn)定匹配、女士最差穩(wěn)定匹配.注5.2.2:男士最優(yōu)穩(wěn)定匹配是女士最差穩(wěn)定匹配;女士最優(yōu)穩(wěn)定匹配是男士最差穩(wěn)定匹配男士求婚的Gale-Shapley算法產(chǎn)生的穩(wěn)定匹配是男士最優(yōu)穩(wěn)定匹配,女士求婚的Gale-Shapley算法產(chǎn)生的穩(wěn)定匹配是女士最優(yōu)穩(wěn)定匹配.注5.2.2:對于男士的“優(yōu)于”關(guān)系是所有穩(wěn)定匹配集合上的一個偏序關(guān)系,其實(shí)所有的穩(wěn)定匹配在此偏序關(guān)系下是一個格.格的最大元是男士最優(yōu)穩(wěn)定匹配,最小元是男士最差穩(wěn)定匹配.對于女士的“優(yōu)于”關(guān)系也有類似的結(jié)果.

最后我們需要指出我們討論的穩(wěn)定婚姻問題有相當(dāng)大的局限性,比如男士和女士人數(shù)相等,每一個人要選擇與其性別相反的人并且是一選一,等等.但實(shí)際中往往沒有這些限制,比如師范院校學(xué)生申請實(shí)習(xí)學(xué)校,首先學(xué)生人數(shù)和學(xué)校數(shù)量不必相同,其次一個學(xué)校一般也可接收多個實(shí)習(xí)生，因此很有必要去討論穩(wěn)定婚姻問題的若干變形.對穩(wěn)定匹配及各種擴(kuò)展感興趣的讀者可以參考由D.Gusfiedl和R.W.Irving編著的Thestablemarriageproblem:structureanda