華羅庚學(xué)校數(shù)學(xué)教材(六年級(jí)下)第08講圖論中的匹配與邏輯推理問題

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

2、加任何推理 地表現(xiàn)于圖上虛線2條，實(shí)線1條，共3條線.現(xiàn)在，有兩個(gè)明顯的事實(shí)；第一，V i中每點(diǎn)有且只有一條實(shí)線與 V2中 相應(yīng)點(diǎn)配對(duì)，V2中每點(diǎn)有且只有一條實(shí)線與 Vi中相應(yīng)點(diǎn)配對(duì).V i內(nèi)部點(diǎn)之間 不會(huì)有線相聯(lián)結(jié)，V 2內(nèi)部點(diǎn)之間也不會(huì)有線相聯(lián)結(jié).第二，從 Vi （或V2）中 某一個(gè)點(diǎn)，例如說 a點(diǎn)如發(fā)出了一條實(shí)線向著 V2 （或Vi）中某一個(gè)點(diǎn)，例 如說x點(diǎn)，那么a點(diǎn)與V2 （或Vi）中其他點(diǎn)之間必然只能用虛線聯(lián)結(jié)（這 是邏輯推理中的排它性）由此，我們很容易將中、日、韓的名次判出. (g) 6這樣的問題，抽象起來可歸屬于圖論中稱之為“二分圖的匹配”問題.圖論的名詞術(shù)語太多，這里不作詳細(xì)定

3、義，只是描述性介紹一下，大 家以前在“一筆畫”等講中已初步接觸.所謂二分圖，就是頂點(diǎn)集合可以劃 分成兩個(gè)部分，V=Vi +V,如Vi有p個(gè)點(diǎn)，記為 Vi二v i ,v 2，v p, V2有 q個(gè)點(diǎn)，記為 V= Vp+l,Vp+2，Vp+q,而Vi中任意一點(diǎn)，不會(huì)與 Vi中其他 點(diǎn)聯(lián)結(jié)，而只能與 V2中某些點(diǎn)聯(lián)結(jié)；V 2也如此.大家看幾個(gè)例.一般的圖記為 0=（V, E） , V是頂點(diǎn)集合，E是邊（也可稱為線）的集 合.大家在哥尼斯堡七橋問題中已領(lǐng)略過這種抽象.現(xiàn)在的二分圖是一類特 殊的圖，只不過頂點(diǎn)集 V劃分為兩部分，而這只能“跨越”于Vi中某個(gè)點(diǎn)和V2中另一個(gè)點(diǎn).二分圖的匹配問題，就是找一個(gè)

4、邊的集合，這些邊之間都沒有公共的端點(diǎn).關(guān)于二分圖的匹配， 要研究的是“最大匹配”，即找一個(gè)邊最多的匹配. 就本講開始引入的問題看，我們還沒有解完，因?yàn)檫€有A、BC三個(gè)代號(hào)到底如何歸于中、日、韓三隊(duì)的問題 一種解題辦法，是把已判出的國 籍和名次捆綁在一個(gè)頂點(diǎn)內(nèi)，如（中2）、（韓i）、（日3）,再和A BC構(gòu) 造一個(gè)新的二分圖:eg) (g3)C)“ 4 顯然，推知B是（日3）,因?yàn)锽有2條虛線，而必然有1條實(shí)線，只 能推出B與（日3）之間為實(shí)線.同理，（韓1）只能為C;剩下的唯一的情 況留給了 A為（中2）.全部問題解決了.再看最初的題目，如果你選擇先判斷中、日、韓和A、BC三個(gè)代號(hào)之間的匹配關(guān)

5、系，將會(huì)怎樣呢？畫一個(gè)圖看，利用已知條件畫出實(shí)、虛線.只能利用B不是韓國隊(duì)及中國隊(duì)第二，B不是第二（因此B不是中國隊(duì)） 這樣一些條件，題目中另二句話：A不是第一名，第一名不是日本隊(duì)，這種否定關(guān)系之間，沒有傳遞性，你不能判定A是不是日本隊(duì).因此根據(jù)已知條件所畫的圖中只有兩條虛線，之后最多只能確定日、B之間為實(shí)線.所以對(duì)這樣的二分圖，無法找出合理的最大匹配.這方法使問題求解走進(jìn)了死胡 同.那么你選擇先判 A、BC和第一、第二、第三名之間的匹配關(guān)系，又 會(huì)怎樣呢？畫一個(gè)圖看. 現(xiàn)在也只有二條虛線，仍然無法找出最大匹配，或說解不唯一，對(duì)求 解問題無助.現(xiàn)在回過頭來看，先找國別與名次之間的匹配，似乎有些

6、“碰運(yùn)氣”， 因?yàn)橥耆梢园杨}目改動(dòng)，使先找國別與名次的匹配無法解決，例如敘述 改為：中、日、韓三足球隊(duì)比賽，已知結(jié)果為：第 1名不是A,第2名不是韓 國隊(duì)也不是B,A不是日本隊(duì)，中國隊(duì)為B,冋A BC,和1、2、3名與各國隊(duì)如何匹配？細(xì)心讀者發(fā)現(xiàn)，這只是把原題中A BC的地位與1、2、3名的地位互換而已.所以現(xiàn)在改動(dòng)后的題目，再先抓“國別”和“名次”的匹配，就 無法求解.但是數(shù)學(xué)要求找出一種解一般問題的方法而不是“碰運(yùn)氣”，而且完全可以找一個(gè)例子，使得無論取國別與名次；或國別與代號(hào)（ A B, C）;或代號(hào)與名次這三類二分圖的匹配都無法求解，而必須找更廣泛意義下的匹 配才能解決，為此先介紹一

7、般的三個(gè)因素一起考慮的“匹配”方法.先結(jié)合前例，將國別用三個(gè)不同點(diǎn)表示于上方，三個(gè)名次點(diǎn)表示于左 下方，三個(gè)代號(hào)點(diǎn)表示于右下方用實(shí)線的肯定關(guān)系和虛線的否定關(guān)系把已 知條件“翻譯”于圖上.我們現(xiàn)在的目的是要尋找一個(gè)捆綁三條實(shí)線邊的一條廣義邊，使每個(gè)國別與一個(gè)名次及一個(gè)代號(hào)捆綁在一起，使問題一次性解決，遵循的原則 有以下4條: 肯定關(guān)系具有排它性（如中二第 2名，則中工第1名，中工第3名, 第2名工日，第2名工韓）. 肯定關(guān)系具有傳遞性（如已知中二第2名，一旦推知肯定關(guān)系第 2名 二A那么中二A. 任意兩個(gè)類別的點(diǎn)之間要建立一種合理的完全匹配 （如國別和名次 之間；名次與代號(hào)之間；國別與代號(hào)之間）

8、. 如果某一點(diǎn)與另一類點(diǎn)中除一點(diǎn)以外都是否定關(guān)系，那么與這一點(diǎn) 只能是肯定關(guān)系.現(xiàn)在把這些原則具體操作于這個(gè)圖上，就能把問題求解，請(qǐng)讀者看圖，不贅述.=去撞已無用的國別與名次間的虛域/度用原則仗）*知丸工韓知尹申用原則（心知R二日j c二韓，衛(wèi)用原則C2）B=3,:摑綁成:出日二3, C=l攝后則原則（3”二中二2這類問題的思想方法上升到圖論中，已經(jīng)可以用一種更抽象的術(shù)語 “超圖”來描述，也就是頂點(diǎn)集合，仍用V來表示，而超圖的邊是一種抽象的“廣義邊”，把原來簡(jiǎn)單邊捆綁在一起形成的一種“捆綁的邊”在這個(gè)具 體例題中，就是要找出一套捆綁邊，每一捆綁邊，捆著一個(gè)國別，一個(gè)名 次，一個(gè)代號(hào)找出三套捆綁

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