圖論中的匹配問題及算法

愿天下有情人終成眷屬!

如果上帝也懂一點(diǎn)數(shù)學(xué)…

圖論中的匹配問題(matchproblem)在組合數(shù)學(xué)中也稱為相異代表系(systemofdistinctrepresentatives).

用集合的語言描述：給定集合族A=(A1,A2,A3,…,An)，希望在每一集合Ai中選出一個(gè)元素ai，使得a1,a2,…,an是相異的n個(gè)元素。我們稱a=(a1,a2,…,an)是A的一個(gè)相異代表系。

用圖的方法描述：每個(gè)集合Ai看作一個(gè)點(diǎn)，集合中每個(gè)元素看作點(diǎn)。如果元素a在集合Ai中，則用線連接aAi。ExampleA1={a,b,c}A2={c,d}A3={b,d}A4={c,d}A1A2A3A4abcdA1——aA2——dA3——bA4——c完美匹配

匹配問題可以有多種解釋，可以把它解釋為委員會(huì)選派代表問題，可以解釋為工作安排問題，也可以解釋為月下老人牽紅線的問題等等。Ai——看成是第i個(gè)女孩可能托付終身的白馬王子集；月老的任務(wù)是要將每位女孩許配給一位白馬王子，但二女不可同配一夫。Ai為做第i個(gè)工作所合適的人員集合，問題就是要為每個(gè)工作尋找一個(gè)工人，但同一人不能做一個(gè)以上的工作。

……為了解問題所在，我們看幾個(gè)例子：EX1A1={a,b,c}，A2={c,d}A3={b,d}，A4={c,d}恰有兩組相異代表系(a,c,b,d)和(a,d,b,c)。

EX2A1={a}A2=, A3={a,b}A4={c,d,e,f,g,h}A={A1,A2,A3,A4}

沒有相異代表系（或不存在一個(gè)匹配飽和A）。Ex3A1={3,4}, A2={3,7,9},A3={2,3}, A4={6,11,12}, A5={4,6,8},A6={2,6,9}, A7={3,4,8},A8={3,5,10,13}, A9={2,3,7,9}, A10={2,8,9}A=(A1,A2,…,A10)

是否存在相異代表系？答案：不存在相異代表系。因?yàn)椋?/p>

A1∪A2∪A3∪A5∪A6∪A7∪A9∪A10={2,3,4,6,7,8,9}

八個(gè)集合只包含七個(gè)元素所以不可能找到一個(gè)相異代表系。Hall’sTheoremA=(A1,A3,…,An)存在一個(gè)相異代表系對所有

恒有證明：必要性顯然，現(xiàn)證條件為充分的。如果對所有恒有，我們可以假設(shè)A是滿足這個(gè)條件的最小集合族。也就是，從任何一個(gè)Ai中去掉任一個(gè)元素所得的新集合族不再滿足上述條件。首先我們證明：所有Ai恰含一個(gè)元素.否則假設(shè)A1含有x及y，但x≠y，則(A1\{x},A2,…,An)和(A1\{y},A2,…,An}都不滿足上述條件，因此存在下標(biāo)集I,J{2,3,…,n}

使得

|X|≤|I|

且|Y|≤|J|其中Hall’sTheoremA=(A1,A3,…,An)存在一個(gè)相異代表系對所有

恒有所以|I|+|J|≥|X|+|Y|=|X∪Y|+|X∩Y|=≥|I∪J∪{1}|+|I∩J|=1+|I∪J|+|I∩J|=1+|I|+|J|Hall’sTheoremA=(A1,A3,…,An)存在一個(gè)相異代表系對所有

恒有這是矛盾！所以每一個(gè)集合Ai={ai}恰含一元素，但因?yàn)镠all’sTheorem條件，所以這些a1,a2,…,an都不相同，因此(a1,a2,…,an)是(A1,A2,…,An)的SDR。Hall’sTheoremA=(A1,A3,…,An)存在一個(gè)相異代表系對所有

恒有Hall定理在矩陣論(MatrixTheory)和擬陣?yán)碚?MatroidTheory)以及組合設(shè)計(jì)(CombinatoricsDesign)中有廣泛應(yīng)用。(婚姻定理1917Frobenius)

A=(A1,A2,…,An)，如果|Ai|=k(k>0)且每個(gè)元素剛好在k個(gè)集合中，則A有 SDR(完美匹配)。A1A2A3A41234二部圖G=(X,Y)正則圖x1x2x3x4y1y2y3y4M={x1y1,x2y2,x4y4}是一個(gè)最大匹配M’={x3y1,x4y2}不是最大匹配x1x2x3x4y1y2y3y4x1x2x3x4y1y2y3y4M’-可增廣路x1,y3未匹配點(diǎn)x1x2x3x4y1y2y3y4x1x2x3x4y1y2y3y4x1x3x4y1y2y3x1x3x4y1y2y3Thm(1931Konig–Egervary)

M是圖G的最大匹配

G不存在M-可增廣路由此定理的證明可設(shè)計(jì)一個(gè)多項(xiàng)式算法來生成圖G的最大匹配(此算法的復(fù)雜度為O(m2n))。指派問題是在加權(quán)完全二部圖中找權(quán)和最大的完美匹配問題，此問題有著名的匈牙利方法(Kuhn,1955),也是多項(xiàng)式算法，也可轉(zhuǎn)化為0-1規(guī)劃來解。

穩(wěn)定匹配問題

Boy{x,y,z,w},Girl{a,b,c,d}x:a>b>c>da:z>x>y>wy:a>c>b>db:y>w>x>zz:c>d>a>bc:w>x>y>zw:c>b>a>dd:x>y>z>w如果你是月下老人，該怎樣為這些男女青年?duì)考t線，使得每一對匹配都是穩(wěn)定的？何謂“不穩(wěn)定”？如果某個(gè)男孩(或女孩)喜愛另一個(gè)女孩(或男孩)比他目前的女朋友(或男朋友)多,同時(shí)他(或她)喜歡的這個(gè)人女孩(男孩)喜歡他(或她)比喜歡她(或他)目前的男朋友(或女朋友)更多一些,則匹配不穩(wěn)定。

Boy{x,y,z,w},Girl{a,b,c,d}x:a>b>c>da:z>x>y>wy:a>c>b>db:y>w>x>zz:c>d>a>bc:w>x>y>zw:c>b>a>dd:x>y>z>wx–by–az–cw-d∵x:a>ba:x>yx<≠>ba<≠>yx<=>a不穩(wěn)定

每個(gè)男孩從沒有拒絕過他的女孩中,向他最喜歡者發(fā)出求愛信號(hào)！

Boy{x,y,z,w},Girl{a,b,c,d}x:a>b>c>da:z>x>y>wy:a>c>b>db:y>w>x>zz:c>d>a>bc:w>x>y>zw:c>b>a>dd:x>y>z>wxyzwabcdxyzwabcdxyzwabcdxyzwabcdxyzwabcd可驗(yàn)證這是一個(gè)穩(wěn)定匹配！如果女孩主動(dòng)，則結(jié)果不一樣abcdzywx也是一個(gè)穩(wěn)定匹配！事實(shí)上，對一般情形，也可以證明：主動(dòng)一方在婚姻中占有優(yōu)勢。前世注定的因緣莫錯(cuò)過思考題：堆場上有若干個(gè)箱區(qū)供出口貨物堆放，出口貨物歸屬于若干遠(yuǎn)洋貨輪。某個(gè)具體箱區(qū)可堆放何艘貨輪的貨物由各種限制確定，但每個(gè)箱區(qū)不能全放同一艘貨輪的貨物。一般地,一艘貨輪的貨物盡量分散在2-3塊箱區(qū)為好。請?jiān)O(shè)計(jì)一個(gè)算法能讓電腦自動(dòng)生成每艘貨輪的貨物堆放箱區(qū)。參考文獻(xiàn)