第5章再論圖論離散數(shù)學(xué)配套教材：李小南目錄CONTENTS6.16.26.36.46.5二部圖最大匹配及穩(wěn)定匹配圖的連通性平面圖圖的頂點著色6.1二部圖

二部圖和匹配有工作申請者和n項工作,每項工作最多由一個人來做且每個人可接受的工作有若干種,能否有一種工作安排方案,使得n個人都能得到自己滿意的工作?可以用圖對這一問題建立模型:圖的頂點分別為申請者和工作,若人a滿意工作j,就用一條邊連接a和j.這樣問題就變?yōu)槭欠窨梢哉页鰊條相互之間無公共頂點的邊.上述模型中圖的頂點集可以分為兩個集合,使得每個集合中的頂點互不相鄰,這樣的圖稱為二部圖,模型中需要尋找的相互無公共頂點的邊集稱為圖的匹配.

定理5.1.1(k?nig,1936)一個圖是二部圖當(dāng)且僅當(dāng)它不含奇圈.證明：必要性.二部圖中的閉合通道都是從某個部集出發(fā)往返于兩個部集間最后再回到出發(fā)的部集,經(jīng)過了偶數(shù)步,也即二部圖的閉合通道都是偶數(shù)長的.故二部圖不含奇圈.定理5.1.1(k?nig,1936)

一個圖是二部圖當(dāng)且僅當(dāng)它不含奇圈.

定理5.1.1(k?nig,1936)

一個圖是二部圖當(dāng)且僅當(dāng)它不含奇圈.證明：充分性.

頂點覆蓋

街道上需要有警察來維持治安,假設(shè)交叉路口的警察可以監(jiān)管和路口相連的街道,我們往往關(guān)心最少安排多少警察可以監(jiān)管整個街道網(wǎng)絡(luò)？把上面問題抽象成圖論中的模型,我們就有了下面頂點覆蓋的概念.

在左圖中，等式成立,而右圖中最小頂點覆蓋大小為3,而最大匹配大小為2.注意左圖為二部圖,其實我們有定理5.1.3定理5.1.3(K?nig-Egerváry,1931)設(shè)G是(X,Y)-二部圖,則G的最大匹配的大小等于G的最小頂點覆蓋的大小.

定理5.1.3(K?nig-Egerváry,1931)設(shè)G是(X,Y)-二部圖,則G的最大匹配的大小等于G的最小頂點覆蓋的大小.

Hall定理有許多證明方法,我們這里利用K?nig-Egerváry定理證明了Hall定理,也可利用Hall定理證明K?nig-Egerváry定理.另外,Hall定理告訴我們可以通過的某些子集的鄰域頂點太少來說明不存在浸潤(X,Y)-二部圖中部集X的匹配.最后我們指出匹配理論是組合數(shù)學(xué)及最優(yōu)化學(xué)科中最經(jīng)典且最為重要的內(nèi)容之一,在諸多領(lǐng)域有著廣泛應(yīng)用.關(guān)于匹配理論更多的介紹可參考由L.Lovász和M.Plummer編著的

MatchingTheory一書.第6.2節(jié)最大匹配及穩(wěn)定匹配離散數(shù)學(xué)講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學(xué)，電子工業(yè)出版社，2025最大匹配由上節(jié)，我們知道對于一個二部圖中的匹配M來說,若圖中沒有M增廣路徑,則M就是最大匹配了.這就為我們提供了一種求最大匹配的方法.設(shè)M是(X,Y)-二部圖G中的一個給定的匹配(可以是空集),如果M不是最大匹配,則一定存在一條M增廣路徑,此路徑一定是從未被M浸潤的X中頂點出發(fā)并終止于Y中未被M浸潤的頂點的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兩種擴展另一種擴展是尋找加權(quán)二部圖中的權(quán)值最大的匹配.Kuhn(1955)解決了這個問題(由于K?nig和Egerváry的工作是上述算法的基礎(chǔ),為了紀念這兩位匈牙利數(shù)學(xué)家,Kuhn把此算法稱為匈牙利算法).注5.2.1兩種擴展穩(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)系,其實所有的穩(wěn)定匹配在此偏序關(guān)系下是一個格.格的最大元是男士最優(yōu)穩(wěn)定匹配,最小元是男士最差穩(wěn)定匹配.對于女士的“優(yōu)于”關(guān)系也有類似的結(jié)果.

最后我們需要指出我們討論的穩(wěn)定婚姻問題有相當(dāng)大的局限性,比如男士和女士人數(shù)相等,每一個人要選擇與其性別相反的人并且是一選一,等等.但實際中往往沒有這些限制,比如師范院校學(xué)生申請實習(xí)學(xué)校,首先學(xué)生人數(shù)和學(xué)校數(shù)量不必相同,其次一個學(xué)校一般也可接收多個實習(xí)生，因此很有必要去討論穩(wěn)定婚姻問題的若干變形.對穩(wěn)定匹配及各種擴展感興趣的讀者可以參考由D.Gusfiedl和R.W.Irving編著的Thestablemarriageproblem:structureandalgorithms一書.值得一提的是,Gale-Shapley算法的提出者之一、著名數(shù)學(xué)家、加州大學(xué)洛杉磯分校的Shapley教授因在博弈論領(lǐng)域的杰出貢獻而獲得了2012年諾貝爾經(jīng)濟學(xué)獎.第6.3節(jié)圖的連通性離散數(shù)學(xué)講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學(xué)，電子工業(yè)出版社，2025連通度不同圖的連通“程度”可能是不同的,有的連通圖(例如完全圖),刪除一些頂點(或邊)后還是連通的;有些連通圖,刪除一個頂點(或邊)就不連通了(例如圈).本節(jié)我們就來研究圖的連通“程度”

前面我們通過刪除頂點來定義連通度,下面我們通過刪除邊來定義連通度.

Menger定理前面我們用任意兩個頂點間有路徑相連來定義連通圖,而兩個頂點間的不同路徑越多,圖的連通程度似乎就越高.下面說明通過這種方式定義連通程度本質(zhì)上和前面刪除頂點的定義方式是等價的.

推論5.3.2

多于兩個頂點的圖是2-連通圖當(dāng)且僅當(dāng)中的任意兩個邊都在某一個圈上.下面我們把定理5.3.2推廣到一般的-連通圖,就得到了經(jīng)典的Menger定理.由于證明較繁,我們這里略去(可參考[1,2,5]).先來介紹一個概念.

連通度

第6.4節(jié)平面圖離散數(shù)學(xué)講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學(xué)，電子工業(yè)出版社，2025歐拉定理及應(yīng)用定義5.4.1一個圖G可以圖示在平面上,使得任何兩邊除了頂點外無公共交點,則稱圖G是可平面圖(planargraph).G的這種圖示也稱為G的一個平面嵌入(planarembedding).一個平面圖(planegraph)是指一個可平面圖的一個特定的平面嵌入.平面圖將平面分成許多區(qū)域,這些由邊圍成的區(qū)域稱為面(face).

注歐拉定理最早是以凸多面體形式給出的.雖然我們是在圖論部分給出的歐拉定理,但還是要指出歐拉公式實際上反應(yīng)了一種拓撲性質(zhì).而歐拉定理的推廣也是拓撲學(xué)中非常重要的結(jié)論之一.拓撲學(xué)和圖論有著密切的聯(lián)系,前面提到的圖論起源問題的格尼斯堡七橋問題也被認為是拓撲學(xué)的起源.關(guān)于歐拉定理的精彩介紹推薦讀者參閱:王敬庚,直觀拓撲(第三版).北京:北京師范大學(xué)出版社,2010.另外對拓撲學(xué)感興趣的同學(xué),推薦:M.A.Armstrong,BasicTopology,Springer,1983(有中譯本).該書從歐拉定理開始,對拓撲學(xué)有引人入勝的介紹.

利用歐拉定理,我們可以給出平面圖邊數(shù)的一個上界

可平面圖的刻畫

例5.3.2證明:Peterson圖(左圖)不是可平面圖.

例5.3.2證明:Peterson圖(左圖)不是可平面圖.

第6.5節(jié)圖的頂點著色離散數(shù)學(xué)講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學(xué)，電子工業(yè)出版社，2025學(xué)校安排補考,需要將有同一個學(xué)生參加的兩門課安排在不同時間.將各門課程作為圖的頂點,若某個學(xué)生需要補考兩門課程,則將這兩門課程對應(yīng)的頂點用邊相連.我們給這樣的圖中每個頂點賦予某種顏色,使得相鄰頂點的顏色不同,則安排考試需要的時間段的最小值等于對圖中頂點進行著色的最少顏色數(shù).計算機在循環(huán)內(nèi)計算時把頻繁使用的變量的值存儲于中央處理器的寄存器中而不是內(nèi)存中,這樣做便于快速訪問數(shù)據(jù)從而提高效率.如果兩個變量在不同時刻使用,則可以分配給它們同一個寄存器.定義一個圖,其頂點就是變量,兩個頂點相鄰當(dāng)且僅當(dāng)對應(yīng)的兩個變量在某時刻同時使用,則變量所需要的寄存器的最少個數(shù)等于給圖中頂點著色使得相鄰頂點的顏色不同所需的最少顏色數(shù).類似的還有裝箱問題:有些貨物裝在同一個箱子里面不安全,給定一些貨物,至少需要多少個箱子來裝?這些問題都和圖的頂點著色有關(guān),下面給出圖的頂點著色的定義.頂點著色的定義和性質(zhì)

例5.5.1左圖是Peterson圖.因為Peterson圖中含有奇圈,故Peterson圖不是二部圖,因此Peterson圖的色數(shù)至少為3.左圖給出了Peterson圖的3種顏色的頂點著色方案（標相同字母的頂點著相同的顏色）,這就說明Peterson圖的色數(shù)為3.右圖為Gr?tzsch圖,圖中給出了4中顏色的著色方案（標相同字母的頂點著相同的顏色）,不難驗證用3種顏色不可能給Gr?tzsch圖著色,故此圖的色數(shù)為4.頂點著色的定義和性質(zhì)

貪婪著色：怎么給一個圖進行頂點著色?下面我們介紹一種稱之為貪婪著色的方法.用1,2,3,…等正整數(shù)來表示顏色.

四色問題四色問題的最初形式是:能否用4種顏色給任意平面區(qū)域著色,使得有公共邊的相鄰區(qū)域有不同的顏色(參見左圖).給每個區(qū)域放置一個頂點,兩個區(qū)域有公共