組合數(shù)學(xué)(第9章9.3).pptx

1、,組合數(shù)學(xué)課程第九章 二分圖中的匹配(3),李建欣 北航計算機學(xué)院 (),2010年6月8日,為什么二分圖？例題1 Place the Robots,問題描述 有一個N*M(N,M=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機器人只能放在空地上。在同一行或同一列的兩個機器人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，最多可以放置多少個機器人，使它們不能互相攻擊。,例題1 Place the Robots,模型一,于是，問題轉(zhuǎn)化為求圖的最大獨立集問題。,在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡

2、單的模型：以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：,例題1 Place the Robots,模型一,在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型： 以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：,這是NP問題！,我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個塊之中，最多只能放一個機器人。我們把這些塊編上號。,同樣，把豎直方向的塊也編上號。,例題1 Place the Robots,模型二,1,2,3,4,5,例題1 Place the Robots,

3、模型二,1,2,3,4,5,把每個橫向塊看作X部的點，豎向塊看作Y部的點，若兩個塊有公共的空地，則在它們之間連邊。,于是，問題轉(zhuǎn)化成這樣的一個二分圖：,由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉(zhuǎn)化為二分圖的最大匹配問題。,例題1 Place the Robots,模型二,1,2,3,5,4,比較前面的兩個模型：模型一過于簡單，沒有給問題的求解帶來任何便利；模型二則充分抓住了問題的內(nèi)在聯(lián)系，巧妙地建立了二分圖模型。為什么會產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對問題分析的角度不同：模型一以空地為點，模型二以空地為邊；其二是由于對原型中要素的選取有差異：模型一對要素的選取不充分

4、，模型二則保留了原型中“棋盤”這個重要的性質(zhì)。由此可見，對要素的選取，是圖論建模中至關(guān)重要的一步。,例題1 Place the Robots,小結(jié),二分圖(Bipartite)的知識點-2,2020/7/23,9,二分圖定義,匹配,最大匹配,交錯路徑,最大匹配 判定方法,覆蓋,匹配邊 最大數(shù),覆蓋頂點 最小數(shù),定理 9.2.1,覆蓋數(shù),引理9.2.2,M交錯路徑 搜索算法,Knig定理,完美匹配,P階正則 二分圖,引理9.2.5,二分圖(Bipartite)的知識點-3,2020/7/23,10,互異代表系統(tǒng) SDR,代表系統(tǒng),成婚條件(MC),SDR子集最大數(shù),穩(wěn)定婚姻,完備婚姻,不穩(wěn)定婚姻

5、,完美匹配,優(yōu)先秩評定矩陣,最大匹配,最小覆蓋,互異代表系統(tǒng),集族A=(A1, A2, An)的元素(e1, e2, en)稱為A的代表系統(tǒng)，其中， Ai是有限集Y的子集， ei Ai. 若滿足eiej(ij), (e1, e2, en)稱為A的互異代表系統(tǒng)，記做SDR.（system of distinct representatives）.,SDR例子,非空集族A=(A1, A2, An)總有代表系統(tǒng)，未必存在SDR。如 A1=a,b,c, A2=a, b, A3=a, b, A4=a, b 這里，A不存在SDR。 A=(A1, A2, An)存在SDR的必要條件是什么？,定理9.3.1：

6、SDR的必要條件,問題背景：配對問題,有n位男士和m位女士，(A1, A2, An)是女士子集的族，Ai是可與第i位男士為配偶的女子集合，i=1,2,n. 那么，一個完備婚姻配對就是(A1, A2, An)的一個SDR， (w1, w2, wn)表示一種配對iwi。 完備婚姻必要條件：任意k位男士的可能配偶集合的并集至少含k位女士。是否充分條件？,二分圖表示,Y= (y1, y2, ym)的子集族A= (A1, A2, An)確定一個二分圖G=(X,Y)，其中，X= (1, 2, n) =(i, yi) | yiAi A有SDRG有n條邊的匹配，即(G)=n.,A1=a,b,c,d, A2=a

7、, b, A3=a, b, A4=a, b,1,2,3,4,a,b,c,d,定理9.3.2：SDR的充要條件,集族A= (A1, A2, An)有SDR當(dāng)且僅當(dāng)成婚條件（MC）成立。 證明：必要性根據(jù)引理9.3.1。 充分性：設(shè)成婚條件成立，只需證明A確定的二分圖G=(X,Y)使得(G)=n，而(G)=c(G)是G的最小覆蓋數(shù)，即：僅需證明不存在頂點數(shù)少于n的覆蓋.,A有SDR,G有n條邊的匹配，即(G)=n.,成婚條件(MC),(G)=c(G)是最小覆蓋,（反證）假設(shè)存在G的一個覆蓋S，|S|n. S可分左、右頂點兩個部分，即令S1=SX, S2=SY, 那么，S1,S2是S的劃分。因此，

8、|S1|+|S2|n 因為|S|n，XS=XS1是非空集合，令|XS1|=k=n-|S1|, XS1=i1, i2, ik, 由于S是G的覆蓋，不存在連接XS1和YS2的頂點的邊，因此,S2,定理9.3.3 :集合存在SDR子集最大數(shù),A= (A1, A2, An)是Y的子集族，選取A中有SDR的子集的最大數(shù),=min|,|+nk: 1kn,i1, i2, ik是1,2,.,n的組合。,這里對應(yīng)A相關(guān)二分圖G的最大匹配數(shù)(G).,最大匹配,最小覆蓋,實例,集合a,b,c,d,e,f的子集族A=(A1, A2, A3, A4, A5, A6)， A1=a,b,c, A2=b,c, A3=b,c,

9、 A4=b,c, A5=c, A6=a,b,c,d,e,f A關(guān)聯(lián)二分圖G，(G)=4,1,2,3,4,5,6,a,b,c,d,e,f,(a,b,c,d)是A中可選的具有SDR集合最多數(shù)，在婚姻問題中，就是可以結(jié)婚的最多男士。該問題也歸為求二分圖的最大匹配問題。 小結(jié)：互異代表系統(tǒng)是二分圖最大匹配的一個應(yīng)用例子。,關(guān)鍵點：配對問題與成婚條件,A=(A1, A2, An)有互異代表系統(tǒng)SDR的充要條件：,|k,|,每個k(1 kn)以及1,2,n的k-組合i1, i2, ik,穩(wěn)定婚姻問題,n位女士和n位男士，每位女士按偏愛程度優(yōu)先序?qū)男士排全序，同樣，每位男士也有一個對女士的排序。那么，組成

10、完備婚姻方式有n!種。 不穩(wěn)定配對：兩女A,B，兩男a,b，若 1）A和a結(jié)婚； 2）B和b結(jié)婚； 3）A更偏愛b而非a； 4）b更偏愛A而非B。,定義：若一個完備婚姻存在不穩(wěn)定配對，稱為該完備婚姻是不穩(wěn)定的，否則稱為穩(wěn)定的完備婚姻。 問題：穩(wěn)定的完備婚姻是否總是存在？,穩(wěn)定婚姻的數(shù)學(xué)模型,二分圖表示 G=(X,Y), 其中X=w1,w2,wn表示女士集合， Y=m1,m2,mn表示男士集合， 是所有可能邊的集合（完全二分圖)。 一個完備婚姻對應(yīng)二分圖G的一個完美匹配。 但這樣二分圖不能表示偏愛順序。,優(yōu)先秩評定矩陣,優(yōu)先秩評定矩陣,m1,m2,mn,w1,w2,wn,1, 2,2, 2,2,

11、 1,1, 1,p, q,i行、j列元素是數(shù)對(p,q) 表示wi給mj排名次p,而mj 給wi排名次為q.,完備婚姻對應(yīng)矩陣不同行、列的所有位置集合。也是n個非攻擊型車的擺放！,例子,1）優(yōu)先秩評定矩陣,m1,m2,w1,w2,1, 2,2, 2,2, 1,1, 1,可能完備婚姻 w1m1, w2m2 w1m2, w2m1 其中第個完備婚姻是穩(wěn)定的，而第個是不穩(wěn)定的。,2）優(yōu)先秩評定矩陣,w1m1, w2m2，w3m3是一個穩(wěn)定的完備婚姻。,延遲認可算法,定理9.4.1 每一個優(yōu)先評定秩矩陣存在穩(wěn)定的完備婚姻。 算法： 初始化：每位女士標(biāo)記落選狀態(tài)。 Do While 存在落選女士 1）每位

12、落選女士在所有未拒絕她的男士選擇排名最優(yōu)男士 2）每位男士在已經(jīng)選擇他且尚未拒絕過的女士中選擇最優(yōu)女士，推遲決定，并拒絕其余女士。,例子,延遲認可算法用于下面優(yōu)先秩評定矩陣。,a,b,A,B,1, 2,2, 1,2, 4,1, 2,c,C,3, 2,3, 1,2, 1,3, 3,4, 3,D,d,4, 1,4, 2,1, 4,1, 3,4, 4,3, 4,2, 3,A,B,C,D,a,b,c,d,男士,例子,1）A選a, B選b, C選d, D選a; a拒絕D.,A,B,C,D,a,b,c,d,算法第一輪,男士,例子,2）D選d；d拒絕C。,a,b,A,B,1, 2,2, 1,2, 4,1,

13、2,c,C,3, 2,3, 1,2, 1,3, 3,4, 3,D,d,4, 1,4, 2,1, 4,1, 3,4, 4,3, 4,2, 3,A,B,C,D,a,b,c,d,算法第二輪,男士,例子,3）C選a；a拒絕A。,a,b,A,B,1, 2,2, 1,2, 4,1, 2,c,C,3, 2,3, 1,2, 1,3, 3,4, 3,D,d,4, 1,4, 2,1, 4,1, 3,4, 4,3, 4,2, 3,A,B,C,D,a,b,c,d,算法第三輪,男士,例子,4）A選b；b拒絕B。,a,b,A,B,1, 2,2, 1,2, 4,1, 2,c,C,3, 2,3, 1,2, 1,3, 3,4,

14、 3,D,d,4, 1,4, 2,1, 4,1, 3,4, 4,3, 4,2, 3,A,B,C,D,a,b,c,d,算法第四輪,男士,例子,5）B選a；a拒絕B。,a,b,A,B,1, 2,2, 1,2, 4,1, 2,c,C,3, 2,3, 1,2, 1,3, 3,4, 3,D,d,4, 1,4, 2,1, 4,1, 3,4, 4,3, 4,2, 3,A,B,C,D,a,b,c,d,算法第五輪,男士,例子,6）B選c。 沒有落選女士，算法結(jié)束,a,b,A,B,1, 2,2, 1,2, 4,1, 2,c,C,3, 2,3, 1,2, 1,3, 3,4, 3,D,d,4, 1,4, 2,1, 4

15、,1, 3,4, 4,3, 4,2, 3,A,B,C,D,a,b,c,d,算法第六輪,得到穩(wěn)定的完備婚姻 Ab, Bc, Ca, Dd,男士,算法分析證明,算法過程：女孩追求男孩，總是選擇她可能最優(yōu)的男孩訂婚，但男士可悔婚。 女孩的每次新的訂婚，得到優(yōu)先級更低的伴侶；而男士每次新的訂婚，得到優(yōu)先級更高的伴侶。 用符號“AaB”表示在a的排名，B優(yōu)先于A； “Ai a”表示在算法的第i輪中， A與a訂婚。那么，若Ai a， Bj a，且ij, 則AaB，其中a是男士，A，B表示女士。,算法證明：算法總能結(jié)束，得到一個完備婚姻。需證明：該完備婚姻是穩(wěn)定的。 對該完備婚姻的任意兩個配對： Aa 和B

16、b。若 A更偏愛b，在算法某輪中（設(shè)i輪），A必然被b拒絕，那么，存在C使得Cib,且AbC, 令算法第k輪結(jié)束，那么Bkb, ik，因此，根據(jù)上述討論CbB，或 C=B. 因此， AbB，b更偏愛B而非A，該婚姻是穩(wěn)定的。證明完成。 穩(wěn)定的完備婚姻是否唯一？一般而言，不必唯一的。在延遲認可算法對調(diào)男女的角色，也可得到穩(wěn)定的完備婚姻。,優(yōu)先秩評定矩陣-例子（1）,1）上述優(yōu)先秩評定矩陣，用男士追求女士算法得到： aC, bA, cB, dD 與女士追求男士算法一致！,優(yōu)先秩評定矩陣-例子（1）,2）優(yōu)先秩評定矩陣 用女士追求男士算法 w1m1, w2m2, w3m3 而用男士追求女士算法： w

17、1m3, w2m1, w3m2 不一致！,算法的優(yōu)先討論,若一個穩(wěn)定完備婚姻中，一個女士的配偶比其他穩(wěn)定完備婚姻中的配對至少有同等優(yōu)先級，則稱該完備婚姻對該女士最優(yōu)。若一個穩(wěn)定完備婚姻對所有的女士都是最優(yōu)的，則稱該完備婚姻是女士最優(yōu)的。類似定義男士最優(yōu)的穩(wěn)定完備婚姻。 問題：女士最優(yōu)（或男士最優(yōu)）的穩(wěn)定完備婚姻是否存在？,最優(yōu)穩(wěn)定完備婚姻問題,定理9.4.2 延遲認可算法中，采用女士主動選擇男士得到穩(wěn)定完備婚姻是女士最優(yōu)的；若用男士主動選擇女士算法，得到的穩(wěn)定完備婚姻則是對男士最優(yōu)的。 證明：規(guī)定術(shù)語：若存在某個穩(wěn)定的完備婚姻中，使得男士M是女士W的配偶，則稱，M對W是可行的，記做WM。需要證

18、明：算法中拒絕了某個女士的那些男士對該女士都不是可行的。即對女士最優(yōu)。,直觀來講：在接受女士A求婚的所有男士中，A能選取一個最優(yōu)的！,對算法的輪數(shù)歸納證明。 1）在第1輪數(shù)結(jié)束時，一個女士A被男士a拒絕，那么有另一個女士B也選擇a，且AaB，這時任何包含Aa配對的完備婚姻都是不穩(wěn)定的，因為：a更偏愛B, 對任何其他男士b, B更偏愛a (因為第一輪選擇a).結(jié)論成立。 2）假設(shè)在k1輪結(jié)束時，沒有女士被對她可行的男士拒絕。,在k+1輪結(jié)束時，設(shè)女士A被a拒絕利于B，即a在該輪選擇B訂婚。根據(jù)歸納假設(shè)，在前k輪中拒絕過B的男士對B都是不可行的，因此，a是對B可行中最優(yōu)的，即若Bb, 則bBa. 現(xiàn)假設(shè)存在穩(wěn)定完備婚姻中A與a配對，而B與b配對，由上討論，a更偏愛B而非A, 且B更偏愛