1、第八講 圖論中的匹配與邏輯推理問(wèn)題先看一個(gè)例題.中、日、韓三個(gè)足球隊(duì)進(jìn)行比賽，已知A不是第一名，B不是韓國(guó)隊(duì)，也不是第二名，第一名不是日本隊(duì)，中國(guó)隊(duì)第二.問(wèn)A、B、C各代表哪國(guó)隊(duì)？各是第幾名？一般解這類(lèi)題都?xì)w于邏輯推理類(lèi)問(wèn)題.我們先來(lái)降低難度.先只要求你判斷出中、日、韓各是第幾名（不必判斷A、B、C）.可以把中、日、韓各用一個(gè)點(diǎn)代表，列于上一行.第一、二、三名各用一個(gè)點(diǎn)代表，列于下一行，記為：V1=中，日，韓，V2=第1名，第2名，第3名. V1中的點(diǎn)與V2中某一個(gè)點(diǎn)有肯定關(guān)系的，就畫(huà)一條實(shí)線(xiàn)，如和.否定關(guān)系的兩點(diǎn)之間畫(huà)一條虛線(xiàn)，如不是；不是.把已知條件不加任何推理地表現(xiàn)于圖上.虛線(xiàn)2條，實(shí)線(xiàn)

2、1條，共3條線(xiàn).現(xiàn)在，有兩個(gè)明顯的事實(shí)；第一，V1中每點(diǎn)有且只有一條實(shí)線(xiàn)與V2中相應(yīng)點(diǎn)配對(duì)，V2中每點(diǎn)有且只有一條實(shí)線(xiàn)與V1中相應(yīng)點(diǎn)配對(duì).V1內(nèi)部點(diǎn)之間不會(huì)有線(xiàn)相聯(lián)結(jié)，V2內(nèi)部點(diǎn)之間也不會(huì)有線(xiàn)相聯(lián)結(jié).第二，從V1（或V2）中某一個(gè)點(diǎn)，例如說(shuō)a點(diǎn)如發(fā)出了一條實(shí)線(xiàn)向著V2（或V1）中某一個(gè)點(diǎn)，例如說(shuō)x點(diǎn)，那么a點(diǎn)與V2（或V1）中其他點(diǎn)之間必然只能用虛線(xiàn)聯(lián)結(jié).（這是邏輯推理中的排它性）由此，我們很容易將中、日、韓的名次判出. 這樣的問(wèn)題，抽象起來(lái)可歸屬于圖論中稱(chēng)之為“二分圖的匹配”問(wèn)題.圖論的名詞術(shù)語(yǔ)太多，這里不作詳細(xì)定義，只是描述性介紹一下，大家以前在“一筆畫(huà)”等講中已初步接觸.所謂二分圖，就是

3、頂點(diǎn)集合可以劃分成兩個(gè)部分，V=V1V2，如V1有p個(gè)點(diǎn)，記為V1=v1，v2，vp，V2有q個(gè)點(diǎn)，記為V2=vp+1，vp+2，vp+q，而V1中任意一點(diǎn)，不會(huì)與V1中其他點(diǎn)聯(lián)結(jié)，而只能與V2中某些點(diǎn)聯(lián)結(jié)；V2也如此.大家看幾個(gè)例. “跨越”于V1中某個(gè)點(diǎn)和V2中另一個(gè)點(diǎn).二分圖的匹配問(wèn)題，就是找一個(gè)邊的集合，這些邊之間都沒(méi)有公共的端點(diǎn).關(guān)于二分圖的匹配，要研究的是“最大匹配”，即找一個(gè)邊最多的匹配.就本講開(kāi)始引入的問(wèn)題看，我們還沒(méi)有解完，因?yàn)檫€有A、B、C三個(gè)代號(hào)到底如何歸于中、日、韓三隊(duì)的問(wèn)題.一種解題辦法，是把已判出的國(guó)籍和名次捆綁在一個(gè)頂點(diǎn)內(nèi)，如（中2）、（韓1）、（日3），再和A、

4、B、C構(gòu)造一個(gè)新的二分圖： 顯然，推知B是（日3），因?yàn)锽有2條虛線(xiàn)，而必然有1條實(shí)線(xiàn)，只能推出B與（日3）之間為實(shí)線(xiàn).同理，（韓1）只能為C；剩下的唯一的情況留給了A為（中2）.全部問(wèn)題解決了.再看最初的題目，如果你選擇先判斷中、日、韓和A、B、C三個(gè)代號(hào)之間的匹配關(guān)系，將會(huì)怎樣呢？畫(huà)一個(gè)圖看，利用已知條件畫(huà)出實(shí)、虛線(xiàn). 只能利用B不是韓國(guó)隊(duì)及中國(guó)隊(duì)第二，B不是第二（因此B不是中國(guó)隊(duì)）這樣一些條件，題目中另二句話(huà)：A不是第一名，第一名不是日本隊(duì)，這種否定關(guān)系之間，沒(méi)有傳遞性，你不能判定A是不是日本隊(duì).因此根據(jù)已知條件所畫(huà)的圖中只有兩條虛線(xiàn)，之后最多只能確定日、B之間為實(shí)線(xiàn).所以對(duì)這樣的二分圖

5、，無(wú)法找出合理的最大匹配.這方法使問(wèn)題求解走進(jìn)了死胡同.那么你選擇先判A、B、C和第一、第二、第三名之間的匹配關(guān)系，又會(huì)怎樣呢？畫(huà)一個(gè)圖看. 現(xiàn)在也只有二條虛線(xiàn)，仍然無(wú)法找出最大匹配，或說(shuō)解不唯一，對(duì)求解問(wèn)題無(wú)助.現(xiàn)在回過(guò)頭來(lái)看，先找國(guó)別與名次之間的匹配，似乎有些“碰運(yùn)氣”，因?yàn)橥耆梢园杨}目改動(dòng)，使先找國(guó)別與名次的匹配無(wú)法解決，例如敘述改為：中、日、韓三足球隊(duì)比賽，已知結(jié)果為：第1名不是A，第2名不是韓國(guó)隊(duì)也不是B，A不是日本隊(duì)，中國(guó)隊(duì)為B，問(wèn)A、B、C，和1、2、3名與各國(guó)隊(duì)如何匹配？細(xì)心讀者發(fā)現(xiàn)，這只是把原題中A、B、C的地位與1、2、3名的地位互換而已.所以現(xiàn)在改動(dòng)后的題目，再先抓“國(guó)

6、別”和“名次”的匹配，就無(wú)法求解.但是數(shù)學(xué)要求找出一種解一般問(wèn)題的方法而不是“碰運(yùn)氣”，而且完全可以找一個(gè)例子，使得無(wú)論取國(guó)別與名次；或國(guó)別與代號(hào)（A，B，C）；或代號(hào)與名次這三類(lèi)二分圖的匹配都無(wú)法求解，而必須找更廣泛意義下的匹配才能解決，為此先介紹一般的三個(gè)因素一起考慮的“匹配”方法.先結(jié)合前例，將國(guó)別用三個(gè)不同點(diǎn)表示于上方，三個(gè)名次點(diǎn)表示于左下方，三個(gè)代號(hào)點(diǎn)表示于右下方.用實(shí)線(xiàn)的肯定關(guān)系和虛線(xiàn)的否定關(guān)系把已知條件“翻譯”于圖上. 我們現(xiàn)在的目的是要尋找一個(gè)捆綁三條實(shí)線(xiàn)邊的一條廣義邊，使每個(gè)國(guó)別與一個(gè)名次及一個(gè)代號(hào)捆綁在一起，使問(wèn)題一次性解決，遵循的原則有以下4條：肯定關(guān)系具有排它性（如中=

7、第2名，則中第1名，中第3名，第2名日，第2名韓）.肯定關(guān)系具有傳遞性（如已知中=第2名，一旦推知肯定關(guān)系第2名=A，那么中=A）.任意兩個(gè)類(lèi)別的點(diǎn)之間要建立一種合理的完全匹配.（如國(guó)別和名次之間；名次與代號(hào)之間；國(guó)別與代號(hào)之間）.如果某一點(diǎn)與另一類(lèi)點(diǎn)中除一點(diǎn)以外都是否定關(guān)系，那么與這一點(diǎn)只能是肯定關(guān)系.現(xiàn)在把這些原則具體操作于這個(gè)圖上，就能把問(wèn)題求解，請(qǐng)讀者看圖，不贅述. 這類(lèi)問(wèn)題的思想方法上升到圖論中，已經(jīng)可以用一種更抽象的術(shù)語(yǔ)“超圖”來(lái)描述，也就是頂點(diǎn)集合，仍用V來(lái)表示，而超圖的邊是一種抽象的“廣義邊”，把原來(lái)簡(jiǎn)單邊捆綁在一起形成的一種“捆綁的邊”.在這個(gè)具體例題中，就是要找出一套捆綁邊

8、，每一捆綁邊，捆著一個(gè)國(guó)別，一個(gè)名次，一個(gè)代號(hào).找出三套捆綁邊，每套與別的套之間沒(méi)有公共的點(diǎn)，也就是超圖的匹配用了這種思想方法，去解決某些邏輯推理問(wèn)題，變的非常快捷而準(zhǔn)確了.再看例子，有A、B、C三位大學(xué)生，一位北京人，一位上海人，一位廣州人，每人的業(yè)余愛(ài)好只是足球、圍棋和歌舞三種中的一種.已知：A不喜歡足球，B不喜歡歌舞；喜歡足球的不是上海人；喜歡歌舞的是北京人；B不是廣州人.請(qǐng)判斷三市人的代號(hào)（指A、B、C）及愛(ài)好.現(xiàn)在把此邏輯推理問(wèn)題，轉(zhuǎn)化為圖論中的“捆綁邊”匹配問(wèn)題，大家不難把此題的圖和我們最初的例比較，它們完全“同構(gòu)”. 答為：B上海人，喜歡圍棋；A喜歡歌舞，北京人；C喜歡足球，廣州人.關(guān)于匹配問(wèn)題本身，有很多問(wèn)題和方法已經(jīng)充分研究和圓滿(mǎn)解決，并找到了可以利用電腦解決的很好的算法.例如從二分圖的求最大匹配算法發(fā)展出稱(chēng)之為“交錯(cuò)路”的方法，直到網(wǎng)絡(luò)上帶權(quán)的最大（或最?。┢ヅ?。習(xí) 題 八1.小明、小強(qiáng)、小華三人參賽迎春杯，分別來(lái)自金城、沙市、水鄉(xiāng)，并分獲一、二、三等獎(jiǎng).現(xiàn)知：小明不是金城選手；小強(qiáng)不是沙市選手；金城選手不是一等獎(jiǎng)；沙市選手得二等獎(jiǎng)；小強(qiáng)不是三等獎(jiǎng)；問(wèn)小華是何處選手，得幾等獎(jiǎng)？2.下面是一個(gè)一般的圖，有9個(gè)點(diǎn)，V=v1，v2，v9，有16條邊，Ee1，e2，e16