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

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

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

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

定理5.1.1(k?nig,1936)

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

頂點(diǎn)覆蓋

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

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

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

Hall定理有許多證明方法,我們這里利用K?nig-Egerváry定理證明了Hall定理,也可利用Hall定理證明K?nig-Egerváry定理.另外,Hall定理告訴我們可以通過的某些子集的鄰域頂點(diǎn)太少來說明不存在浸潤(rùn)(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é)，我們知道對(duì)于一個(gè)二部圖中的匹配M來說,若圖中沒有M增廣路徑,則M就是最大匹配了.這就為我們提供了一種求最大匹配的方法.設(shè)M是(X,Y)-二部圖G中的一個(gè)給定的匹配(可以是空集),如果M不是最大匹配,則一定存在一條M增廣路徑,此路徑一定是從未被M浸潤(rùn)的X中頂點(diǎn)出發(fā)并終止于Y中未被M浸潤(rùn)的頂點(diǎn)的M交錯(cuò)路徑.

輸入:

(X,Y)-二部圖.G的一個(gè)匹配M,U=X-V(M).

例5.2.1考慮圖(a)中的二部圖.二部圖的一個(gè)匹配用粗邊M給出.下面就利用最大匹配算法從此匹配開始尋找一個(gè)最大匹配.(a)(b)

(a)(b)(c)(d)

(c)(d)

注5.2.1兩種擴(kuò)展另一種擴(kuò)展是尋找加權(quán)二部圖中的權(quán)值最大的匹配.Kuhn(1955)解決了這個(gè)問題(由于K?nig和Egerváry的工作是上述算法的基礎(chǔ),為了紀(jì)念這兩位匈牙利數(shù)學(xué)家,Kuhn把此算法稱為匈牙利算法).注5.2.1兩種擴(kuò)展穩(wěn)定匹配

Gale-Shapley算法:每個(gè)男士(女士)按照喜好順序給每個(gè)女士(男士)排序.最喜歡的排在第一位,依次排列.每位男士向排在第一位的女士求婚.某個(gè)女士若有多個(gè)追求者,則該女士與她的排序最前面的男士訂婚.若某個(gè)女士只有一個(gè)追求者,則訂婚.若所有男士都訂婚,則算法終止.剩下的男士(即還沒有訂婚者)繼續(xù)向排在第二位的女士求婚.每位女士在新求婚者,未婚夫(如果在上一步已訂婚)中尋找排序最前面的男士訂婚.繼續(xù)上面的過程,即還未訂婚的男士向還未追求過的最喜歡的女士求婚.而每位女士在新求婚者,未婚夫(如果已訂婚)中尋找排序最前面的男士訂婚.若每個(gè)男士都已訂婚(當(dāng)然同時(shí)每位女士也已訂婚)時(shí),算法終止.

注:算法每個(gè)階段分二步,一是男士求婚,二是女士選擇;每一階段,都有可能某位女士沒有一人追求,因此也不用做出選擇;女士可以悔婚,也即在上一步已經(jīng)訂婚,下一步若遇到更心儀的追求者,可以和后者訂婚,和上一步的訂婚者悔婚.Gale-Shapley算法例5.2.2假設(shè)有4個(gè)男士和4個(gè)女士,他們之間的喜好程度由下表給出.現(xiàn)在我們來說明Gale-Shapley算法怎么給出一個(gè)穩(wěn)定匹配.

注5.2.2每個(gè)穩(wěn)定婚姻問題中存在穩(wěn)定匹配且穩(wěn)定匹配未必唯一.若將Gale-Shapley算法變?yōu)榕壳蠡?則得到的穩(wěn)定匹配和男士求婚的穩(wěn)定匹配未必一樣.且男士或女士求婚的Gale-Shapley算法只能找到所有穩(wěn)定匹配中的兩個(gè).利用Gale-Shapley算法可能得到兩個(gè)穩(wěn)定匹配,那么這兩個(gè)穩(wěn)定匹配在所有穩(wěn)定匹配中的“地位”怎么樣?或者說這兩個(gè)穩(wěn)定匹配和其它穩(wěn)定匹配(如果有的話)的關(guān)系如何?為了回答這個(gè)問題,我們先介紹幾個(gè)概念.

類似可定義男士最差的穩(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:對(duì)于男士的“優(yōu)于”關(guān)系是所有穩(wěn)定匹配集合上的一個(gè)偏序關(guān)系,其實(shí)所有的穩(wěn)定匹配在此偏序關(guān)系下是一個(gè)格.格的最大元是男士最優(yōu)穩(wěn)定匹配,最小元是男士最差穩(wěn)定匹配.對(duì)于女士的“優(yōu)于”關(guān)系也有類似的結(jié)果.

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

前面我們通過刪除頂點(diǎn)來定義連通度,下面我們通過刪除邊來定義連通度.

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

推論5.3.2

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

連通度

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

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

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

可平面圖的刻畫

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

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

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

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

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

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