離散生期末題集合論與圖論gra

1、第三章連通度和匹配 基本內(nèi)容 頂點(diǎn)連通度和邊連通度 門格爾定理 匹配、霍爾定理3.3 霍爾定理（相異性條件）定理1 設(shè)G=(V1V2，E)是一個(gè)偶圖，|V1|V2|。G中存在從V1到V2的完全匹配充分必要條件是V1中任意k個(gè)頂點(diǎn)(k=1,2, |V1|)至少與V2中的k個(gè)頂點(diǎn)相連接。該條件稱為相異性條件例4 現(xiàn)有4名教師：張、王、李、趙，要求他們?nèi)ソ?門課程：數(shù)學(xué)、物理、電工和計(jì)算機(jī)科學(xué)。已知張能教數(shù)學(xué)和計(jì)算機(jī)科學(xué)；王能教物理和電工；李能教數(shù)學(xué)、物理和電工；趙只能教電工。如何安排才能使4位教師都能教課，并且每門課都有人教？共有幾種方案？ 用相異性條件判斷一個(gè)偶圖是否存在完全匹配常常很不方便，下

2、面的充分條件比較便于實(shí)際應(yīng)用。定理2 設(shè)G=(V1V2，E)是一個(gè)偶圖，|V1|V2|。G中存在從V1到V2的完全匹配的充分條件是存在正整數(shù)t，使得V1中每個(gè)頂點(diǎn)的度大于等于t，V2中每個(gè)頂點(diǎn)的度小于等于t。該條件稱為t條件。 定理3 從t條件可以推出相異性條件。 證: 對(duì)于V1中的任意的v1，v2，vr，與它們關(guān)聯(lián)的頂點(diǎn)個(gè)數(shù)m，從v1，v2，vr到V2的邊數(shù)為e。根據(jù)t條件：v1中的每個(gè)頂點(diǎn)至少和t個(gè)頂點(diǎn)相關(guān)聯(lián)，則ert。V2中的每個(gè)頂點(diǎn)至多和V1中的t個(gè)頂點(diǎn)相關(guān)聯(lián)，則emt。故有，mtrt，即mt，結(jié)論成立。注意：定理3中反過來不能推出t條件。推論1 任何r-正則偶圖G(V1V2，E)必有

3、一個(gè)完美匹配，其中r1。例某年級(jí)共開設(shè)7門課程，由7位教師承擔(dān)。已知每位教師都能擔(dān)任其中的3門課程。他們將自己能擔(dān)任的課程報(bào)到教務(wù)處后，教務(wù)處人員發(fā)現(xiàn)每門課都恰好有3位教師能擔(dān)任。問教務(wù)處人員能否安排這7位教師每人擔(dān)任1門課，并且每門課都有人承擔(dān)。第四章 平面圖和圖的著色本章內(nèi)容：平面圖及其歐拉公式 非哈密頓平面圖（不要求） 和圖的著色 庫(kù)拉托斯基定理、對(duì)偶圖 圖的頂點(diǎn)著色 圖的邊著色（不要求）第一節(jié) 平面圖及其歐拉公式內(nèi)容：背景、平面圖、面、偶拉公式、推論1.1 背景 在圖論的理論研究和實(shí)際應(yīng)用中，需要考慮一個(gè)圖能否畫在平面上使得它的邊僅在端點(diǎn)相交的問題。若一個(gè)圖能畫在平面上使得它的邊僅可能

4、在端點(diǎn)相交，則這個(gè)圖稱為平面圖。于是在實(shí)際問題中，判斷一個(gè)圖是否是一個(gè)平面圖是非常重要的。 例1在印刷電路的布線中，感興趣的是知道一個(gè)特定的電網(wǎng)絡(luò)是否可以嵌入平面上。 例2 如圖所示（書上）H1，H2，H3表示三座樓房，W，G和E分別表示自來水廠、煤氣管道和地下電纜。為了安全起見，要求這些管道不能直接接觸交叉。書上圖顯然不是個(gè)好的設(shè)計(jì)方案。但工程設(shè)計(jì)要求能達(dá)到嗎？ 這就提出了這個(gè)圖是否為平面圖的問題。 例3 地圖的著色（四色問題） 一個(gè)圖可以用它的圖解來表示，把一個(gè)圖的圖解就看成是這個(gè)圖本身。但對(duì)一個(gè)給定的圖，其圖解的畫法并不唯一，即從幾何圖形上看可以很不一樣。一個(gè)圖的圖解不僅可以畫在一個(gè)平面

5、上，還可以畫在球面上或任一給定的曲面上。 下面將考慮這樣一類圖，其圖解畫在一個(gè)平面上時(shí)，有一種畫法能使其邊僅可能在頂點(diǎn)相交，而在邊的內(nèi)部不相交，這種圖稱為平面圖。1.2 平面圖、面定義1 若G的圖解已畫在平(曲)面S上，而且任何兩條邊均不相交(除可能在端點(diǎn)相交外)，則圖G稱為嵌入平(曲)面S內(nèi)。已嵌入平面S內(nèi)的圖稱為平面圖。若一個(gè)圖可以嵌入平面，則稱此圖是可平面的 說明：可平面圖：能畫在平面上 ，但還沒有畫；平面圖：已經(jīng)畫在平面上了。以后這兩個(gè)概念不加區(qū)分。例如：圖K4是可平面的，因?yàn)镵4的一種平面嵌入法 ；圖K5沒有平面嵌入法； K5畫不出來，并不等于就是非平面圖，必須證明。實(shí)際上，K5是典

6、型的不可平面圖，還有K3，3。定義2 平面圖G把平面分成了若干個(gè)區(qū)域，這些區(qū)域都是連通的，稱之為G的面，其中無界的那個(gè)連通區(qū)域稱為G的外部面，其余的單連通區(qū)域稱為G的內(nèi)部面。說明：(1)平面圖的每個(gè)內(nèi)部面都是G的某個(gè)回路圍成的單連通區(qū)域； (2)一個(gè)平面圖可以沒有內(nèi)部面，但必有外部面，而且外部面唯一；例如：樹作為平面圖就沒有內(nèi)部面。(3)圖K4所示的圖有4個(gè)面，f4是外部面，f1，f2，f3都是內(nèi)部面。 1.3 歐拉公式定理1(歐拉公式)設(shè)G=(p，q)是平面連通圖，有f個(gè)面，則p-q+f=2。證：用數(shù)學(xué)歸納法證明，施歸納于面f的個(gè)數(shù)：注意：定理中的連通性是重要的。若G不連通，則定理不成立。但

7、卻有下面的結(jié)論。推論：設(shè)G=(p，q)是一個(gè)具有f個(gè)面、k個(gè)分支的平面圖，則p-q+f=k+11.4 歐拉公式的推論這些推論都是平面圖的必要條件，不是充分條件。推論1 若G=(p，q)是平面連通圖且每個(gè)面都是由長(zhǎng)為n的回路圍成的，則q=n(p-2)/(n-2) 一個(gè)最大可平面圖是一個(gè)可平面圖，對(duì)此可平面圖中不能再加入邊而不破壞可平面性。推論2 設(shè)G=(p，q)是一個(gè)最大可平面圖，則G的每個(gè)面都是三角形，而且q=3p-6。推論3 若G=(p，q)是一個(gè)可平面連通圖，而且G的每個(gè)面都是一個(gè)長(zhǎng)為4的回路圍成的，則q=2p-4推論4 若G=(p，q)是一個(gè)連通的平面圖，p3，則q3p6。 若G是2連通

8、的且沒有三角形，則q2p4。推論5 證明K5和K3，3都不是可平面圖。 推論6 每個(gè)平面圖G的頂點(diǎn)度的最小值不超過5，即(G)5 。 第二節(jié) 庫(kù)拉托斯基定理、對(duì)偶圖 內(nèi)容：細(xì)分圖、收縮圖、二度結(jié)點(diǎn)內(nèi)的同構(gòu)、初等收縮、對(duì)偶替已經(jīng)證明：(1) K5和K3，3不是平面圖，而K5和K3，3的每個(gè)真子圖顯然都是平面圖；（ （2）顯然，平面圖的每個(gè)子圖是平面圖。因此，平面圖中不含子圖K5和K3，3。2.1 細(xì)分圖定義1 設(shè)G=(V，E)是一個(gè)圖，則（1）若x=uv是圖G一條邊，又w不是G的頂點(diǎn)，則當(dāng)用uw和wv代替邊x時(shí)，就稱邊x被細(xì)分。（2）若G的某些條邊被細(xì)分，產(chǎn)生的圖稱為G的細(xì)分圖，也稱為二度頂點(diǎn)內(nèi)

9、細(xì)分圖。定義2 若兩個(gè)圖可以從一個(gè)圖通過一系列的邊細(xì)分得到，這兩個(gè)圖稱為同胚的(homeomorphism)，也稱為二度頂點(diǎn)內(nèi)同胚。例如：兩個(gè)回路是同胚的。于是，一個(gè)圖若含有同胚于K5或K3，3的子圖，它就不是平面圖。庫(kù)拉托斯基指出，這個(gè)必要條件也是充分的。定理1(庫(kù)拉托斯基，1930)一個(gè)圖是可平面的充分必要條件是它沒有同胚于K5或K3，3的子圖。 平面圖還存在著若干其他特征。 為了描述另外的特征，引入下面定義。2.2 收縮圖定義3 設(shè)G=(V，E)是一個(gè)圖，則(1)若uw和wv是圖G的兩條邊且deg(w)=2，用一條邊uv代替uw和wv時(shí)，則稱uw和wv被縮減。(2)若G的某些條邊被縮減，

10、產(chǎn)生的圖稱為G的縮減圖，也稱二度頂點(diǎn)內(nèi)縮減圖。1937年，瓦格納(K.W.agner)證明了：定理2 一個(gè)圖是可平面的當(dāng)且僅當(dāng)它沒有一個(gè)可以收縮到K5或K3，3的子圖。2.3 二度結(jié)點(diǎn)內(nèi)的同構(gòu)定義4 給定兩個(gè)圖G1和G2，若它們是同構(gòu)的，或者通過反復(fù)插入或除去度為2的頂點(diǎn)后，使得G1和G2同構(gòu)，則稱這兩個(gè)圖是2度頂點(diǎn)內(nèi)同構(gòu)。定理3 一個(gè)圖是可平面圖充分必要條件是圖G不包含與K5或K3，3在二度頂點(diǎn)內(nèi)同構(gòu)的子圖。2.4 初等收縮定義5 一個(gè)圖G的一個(gè)初等收縮由等同兩個(gè)鄰接的頂點(diǎn)u和v得到，即從G中去掉u和v，然后再加上一個(gè)新的頂點(diǎn)w，使得w鄰接于所有鄰接于u和v的頂點(diǎn)。一個(gè)圖G可收縮到圖H，若H

11、可以從G經(jīng)一系列的初等收縮得到。2.5 對(duì)偶圖定義6 設(shè)G=(V，E)是一個(gè)平面圖，由G按如下方法構(gòu)造一個(gè)圖G*，G*稱為G的對(duì)偶圖： (1)對(duì)G的每個(gè)面f對(duì)應(yīng)地有G*的一個(gè)頂點(diǎn)f*； (2)對(duì)G的每條邊e對(duì)應(yīng)地有G*的一條邊e*：G*的兩個(gè)頂點(diǎn)f*與g*由邊e*聯(lián)結(jié)，當(dāng)且僅當(dāng)G中與頂點(diǎn)f*與g*對(duì)應(yīng)的面f與g有公共邊e，若某條邊x僅在一個(gè)面中出現(xiàn)而不是兩個(gè)面的公共邊，則在G*中這個(gè)面對(duì)應(yīng)的頂點(diǎn)有一個(gè)環(huán)。 (3)當(dāng)平面G已畫在平面上時(shí)，G的對(duì)偶圖如下構(gòu)造：在G的每個(gè)面內(nèi)放一個(gè)頂點(diǎn)，若兩個(gè)面有一條公共邊x，則用一條僅僅穿過邊x的邊x*來聯(lián)相應(yīng)的頂點(diǎn)。這樣總產(chǎn)生一個(gè)平面?zhèn)螆D。在圖中，G的邊是實(shí)線，

12、頂點(diǎn)是小圓圈，而G的對(duì)偶圖G*的邊用虛線畫出，頂點(diǎn)用實(shí)心黑點(diǎn)畫出。說明：(1)顯然，G*有一個(gè)環(huán)當(dāng)且僅當(dāng)G有一條橋；而G*有多重邊當(dāng)且僅當(dāng)G的兩個(gè)面至少有兩條公共邊。(2) 若G是一個(gè)有p個(gè)頂點(diǎn)和q條邊及f個(gè)面的平面連通圖，則G的對(duì)偶圖G*也是一個(gè)平面圖；若G不是平面連通圖， G的對(duì)偶圖G*也是一個(gè)平面圖。(3)若G*是連通平面圖：頂點(diǎn)數(shù)、邊數(shù)和面數(shù)分別記為p*，q*和f*，則 p*=f，q*=q，f*=p。 若G不是連通平面圖：則 p*=f ，q*=q，f*=p-k+1。 (4) 由于一個(gè)抽象的可平面圖嵌入平面上時(shí)，可能有不只一種嵌入方法，因而產(chǎn)生了不只一個(gè)對(duì)偶圖。盡管G的不同嵌入法得到的平

13、面圖是同構(gòu)的，但不同嵌入產(chǎn)生的平面圖的對(duì)偶圖可能不同構(gòu)。例如（書上）圖(a)和(b)是同一個(gè)可平面圖G的兩種不同方法嵌入平面，G中的頂點(diǎn)和邊分別用小圓圈和實(shí)圓圈畫出，而它們的對(duì)偶圖G*分別在同一圖上用黑點(diǎn)和虛線畫出頂點(diǎn)和邊。由于(a)中有一面是五條邊圍成的，而(b)沒有這樣的面，所以(a)產(chǎn)生的對(duì)偶圖中有一個(gè)頂點(diǎn)度為5，而(b)產(chǎn)生的對(duì)偶圖中沒有度為5的頂點(diǎn)，所以這兩個(gè)對(duì)偶圖不同構(gòu)。 定義7 若一個(gè)平面圖與它的對(duì)偶圖同構(gòu)，則稱這個(gè)平面圖是自對(duì)偶的。 2.6 例題：例1 判斷下面命題的對(duì)錯(cuò)，并說明理由。任何平面圖G的對(duì)偶圖G*的對(duì)偶圖G*與G同構(gòu)。分析：這個(gè)題目應(yīng)該仔細(xì)鉆研，結(jié)論也值得記憶。證：

14、非連通的平面圖G的對(duì)偶圖G*的對(duì)偶圖G*與G不同構(gòu)因?yàn)镚不連通，而G*連通和G*連通，所以非連通的平面圖G的對(duì)偶圖G*的對(duì)偶圖G*與G不同構(gòu)例7 把平面分成n個(gè)區(qū)域，每?jī)蓚€(gè)區(qū)域都相鄰，問n最大為多少？證：在每個(gè)區(qū)域放一個(gè)頂點(diǎn)，當(dāng)兩區(qū)域相鄰時(shí)，就在相鄰的兩個(gè)頂點(diǎn)間連一條邊，如此構(gòu)造了一個(gè)平面圖且是完全平面圖，而最大的完全平面圖為K，所以n最大為4。例給出平面圖G的對(duì)偶圖G*為歐拉圖的一個(gè)充分必要條件。并證明之。分析：當(dāng)且僅當(dāng)G中每個(gè)面均由偶數(shù)條邊圍成，因?yàn)槠矫鎴DG的每個(gè)面對(duì)應(yīng)G*的每個(gè)頂點(diǎn)，而G*為歐拉圖的充要條件是G*每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)，圍成G每個(gè)面的邊數(shù)與對(duì)應(yīng)的G*中的頂點(diǎn)的度數(shù)相等，所以

15、一個(gè)平面圖G的對(duì)偶圖G*是歐拉圖.證：當(dāng)且僅當(dāng)G中每個(gè)面均由偶數(shù)條邊圍成，一個(gè)平面圖G的對(duì)偶圖G*是歐拉圖。顯然G*是連通圖。設(shè)v*為G*中任意一頂點(diǎn)，v*處于G的面R中，因?yàn)镽由偶數(shù)條邊圍成，所以v*的度數(shù)為偶數(shù)。由于v*的任意性可知。G*為歐拉圖。反之也成立。例設(shè)G為連通的簡(jiǎn)單平面圖，頂點(diǎn)數(shù)為n，面數(shù)為r，證明：若n3，則r2n-4；(2)若G中頂點(diǎn)最小的度為4，則G中至少有6個(gè)頂點(diǎn)的度數(shù)小于等于5。 證:(1)根據(jù)歐拉公式n-m+r=2，其中n，m，r分別是G的頂點(diǎn)數(shù)、邊數(shù)和G的面數(shù)。得r=m+2-n，而對(duì)于頂點(diǎn)數(shù)n3的連通的簡(jiǎn)單的平面圖G，有m3n-6。所以，r2n-4； (2) 假設(shè)

16、G中至多含有5個(gè)頂點(diǎn)的度數(shù)小于等于5。又因?yàn)?G)=4，所以由degvim，得m=degvi54+6(n-5)，所以m3n-5。從而 3n-53n-6，矛盾；所以，G中至少有6個(gè)頂點(diǎn)的度數(shù)小于等于5。例 設(shè)無向圖G是n（n2）個(gè)頂點(diǎn)的極大平面圖，證明：G的對(duì)偶圖G*的邊連通度(G)2，并且G*是3-正則圖。分析：要證明圖G的對(duì)偶圖G*的邊連通度(G)2，也就是說任意刪去G*的一條邊，G*還是連通的。任意圖G的對(duì)偶圖G*都是連通的，并且對(duì)于任意頂點(diǎn)數(shù)大于等于3的極大平面圖所有面的邊數(shù)均為3。所以圖G*是3-正則圖。 證：因?yàn)闊o向圖G是n2個(gè)頂點(diǎn)的極大平面圖，所以圖G的所有面的邊數(shù)均為。根據(jù)平面圖

17、的對(duì)偶圖定義，對(duì)偶圖G*的每個(gè)頂點(diǎn)的度數(shù)degv*=3，所以G*是-度正則圖。 要證明圖G的對(duì)偶圖G*的邊連通度（G）2，等價(jià)于證明：任意刪去G*的一條邊e*（設(shè)圖為G1*），G1*還是連通的。設(shè)e*的兩端點(diǎn)分別為u*，v*。并設(shè)圖G中u*和v*對(duì)應(yīng)的平面分別為r1，r2。顯然r1和r2 是相鄰的，因?yàn)閳DG的平面數(shù)是有限的，且所有的面都由三條邊圍成，所以不走e*，從r1一定存在到r2的路。所以G1*也是連通的，即G的對(duì)偶圖G*的邊連通度(G)2。例10設(shè)簡(jiǎn)單平面圖G中頂點(diǎn)數(shù)n=7,邊數(shù)m=15,證明G是連通的。證：用反證法。設(shè)G不是連通的，則G至少包含兩個(gè)連通分支G1，G2，Gk，k2。設(shè)Gi

18、 的頂點(diǎn)數(shù)為ni，邊數(shù)為mi，i=1，2，k 。 若存在ni=1，則k必為2，因?yàn)橹挥写藭r(shí)G為一個(gè)平凡圖并上一個(gè)K6才能使其邊數(shù)為15，可是K6不是平面圖（它的子圖K5已不是平面圖），這與G是平面圖矛盾，所以ni1。 若存在ni=2，則Gi中至多有一條邊（因?yàn)镚為簡(jiǎn)單圖），另外5個(gè)頂點(diǎn)構(gòu)成K5時(shí)邊數(shù)最多，但充其量為10條邊，這與G有15條邊矛盾。綜上所述，ni3，于是由mi3ni-6 ，i=1，2，k，求和得： m3n-6k （1）將n=7，m=15代入（1）得：1521-6k。即k1，這與k2矛盾。因此G必為連通圖。例12 設(shè)G是面數(shù)r12的簡(jiǎn)單平面圖，G中每個(gè)頂點(diǎn)的度數(shù)至少為3。(1) 證

19、明G中存在至多由4條邊圍成的面；(2) 給出一個(gè)例子說明，若G中的面數(shù)為12，且每個(gè)頂點(diǎn)的度至少為3，則(1)的結(jié)論不成立。證：(1)不妨設(shè)G是連通的，否則可以對(duì)它的每個(gè)連通分支進(jìn)行討論。因而由歐拉公式有: n-m+r=2 （1）又由已知條件知道r12 且 n2m/3 （2）將式（2）的結(jié)果代入式（1）得22m/3m+12 得m30 （3）若所有的面均至少由5條邊圍成，則5r2m 得 r2m/5 (4）將式（2），（4）的結(jié)果代入式（1）得22m/3-m+2m/5 得 m30 （5）式（3）與式（5）矛盾，因而必存在至多由4條邊圍成的面。 (2)十二面體圖有12個(gè)面，每個(gè)頂點(diǎn)均為3度，每個(gè)面由5條邊圍成，并沒有4條邊圍成的面。 例14 證明:當(dāng)每個(gè)頂點(diǎn)的度數(shù)大于等于3時(shí)，不存在有7條邊的簡(jiǎn)單連通平面圖。 證：設(shè)G=(n，m)為簡(jiǎn)單連通平面圖，有r個(gè)面。 若m=7，由歐拉公式知n+r=m+2=9 (1