離散數(shù)學(xué)平面圖課件

1、離 散 數(shù) 學(xué)離 散 數(shù) 學(xué)12圖的基本概念路與回路4歐拉圖與漢密爾頓圖平面圖6對偶圖與著色 圖論 3圖的矩陣表示57樹與生成樹12圖的基本概念路與回路4歐拉圖與漢密爾頓圖平面圖6對偶圖與3定義1：設(shè)G=是一個(gè)無向圖，如果能把G的所有結(jié)點(diǎn)和邊畫在平面上，且使得任何兩條邊除了端點(diǎn)外沒有其他的交點(diǎn)，就稱G是一個(gè)平面圖。 平面圖基本概念 平面圖平面圖非平面圖(1)(2)(3)3定義1：設(shè)G=是一個(gè)無向圖，如果能把G的所有結(jié)點(diǎn)4定義21) 設(shè)G是一連通平面圖，由圖中的邊所包圍的區(qū)域，在區(qū)域內(nèi)既不包含圖的結(jié)點(diǎn)，也不包含圖的邊，這樣的區(qū)域稱為G的一個(gè)面，包圍該面的邊所構(gòu)成的回路稱為這個(gè)面的邊界。2) 面邊

2、界的回路長度稱作該面的次數(shù)，記作deg(r) 。3) 若面的面積有限稱為有限面，否則稱為無限面。每個(gè)平面圖有一個(gè)無限面。例如：右圖每個(gè)面的次數(shù)為： 平面圖基本概念 ABCDEFr1r2r3r4r5Deg(r1)=3 Deg(r2)=3Deg(r3)=5 Deg(r4)=4Deg(r5)=3e1e3e24定義2 平面圖基本概念 ABCDEFr1r2r3r4r5D5定理1：一個(gè)有限平面圖，面的次數(shù)之和等于邊數(shù)的2倍， 即：deg(r)=2|E| 平面圖基本性質(zhì) 證明：eE,e只能以下面兩種情況存在：1.e作為兩個(gè)面的公共邊界2.e作為一個(gè)面的邊界以上兩種情況中，e都被重復(fù)計(jì)算兩次，所以公式成立。A

3、BCDEFr1r2r3r4r55定理1：一個(gè)有限平面圖，面的次數(shù)之和等于邊數(shù)的2倍， 平面定理2(歐拉定理)：連通平面圖G，共有v個(gè)結(jié)點(diǎn)e條邊和r個(gè)面，則歐拉公式：v-e+r=2成立。證明：1)若G為平凡圖，則v=1,e=0,r=1，v-e+r=2成立。2)若G為一條邊，則具有以下兩種情況。v=3,e=2,r=1,v-e+r=23)若G為兩條邊，則有下述幾種情況：v=2,e=1,r=1，v-e+r=2v=1,e=1,r=2，v-e+r=2v=2,e=2,r=2，v-e+r=2v=2,e=2,r=2v-e+r=2v=1,e=2,r=3,v-e+r=2定理2(歐拉定理)：連通平面圖G，共有v個(gè)結(jié)點(diǎn)

4、e條邊和r個(gè)面4)設(shè)G為k條邊時(shí)公式成立，即vk-ek+rk=2成立，則證明在G為k+1條邊時(shí)是否成立：而：G為k條邊，再添加一條邊，只有下述兩種情況：面數(shù)不變點(diǎn)樹加1邊數(shù)加1(Vk+1)-(ek+1)+rk=2成立點(diǎn)數(shù)不變面數(shù)加1邊數(shù)加1(Vk)-(ek+1)+(rk+1)=2成立通過上述歸納法證明歐拉公式v-e+r=2成立。4)設(shè)G為k條邊時(shí)公式成立，即vk-ek+rk=2成立，則證8例1：證明K3,3不是平面圖 證：假設(shè)K3,3是平面圖，則滿足歐拉公式 v e + r = 2 即：6-9+r=2，解得r=5又因?yàn)槿稳3,3中三個(gè)結(jié)點(diǎn)，至少有兩個(gè)點(diǎn)不鄰接，所以不能組成一個(gè)面，即K3,3中

5、任何 一個(gè)面至少由四條邊圍成，即：所有面 的次數(shù)之和deg(r) =4r=20又由定理1知：deg(r)=2|E|=18即18=20矛盾。所以K3,3不是平面圖。 平面圖基本性質(zhì) 不論怎么畫，總有交叉點(diǎn)8例1：證明K3,3不是平面圖 證：假設(shè)K3,3是平面定理3：設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡單平面圖，若v3,則：e=3v-6。證明：設(shè)G的面數(shù)為r,當(dāng)v=3,e=2時(shí)，滿足e=3v-6，即2=3*3-6=3若v3,e3時(shí)，連通簡單G中每一個(gè)面的次數(shù)deg(ri)3G的總次數(shù)deg(ri)=2|E|3r,即2e3r,代入歐拉公式可得：e=3v-6。定理3：設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡單

6、平面圖，若v3例題：證明k5圖不是平面圖。設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡單平面圖，若v3,則：e=3v-6。等價(jià)于:若不滿足e=3v-6，則G不是連通平面圖。K5圖中,v=5,e=10,10 3*v-6=35-6=9K5為非平面圖 平面圖基本性質(zhì) 但定理的條件只是必要條件。如K3,3中v= 6,e =9, e=5，所以deg(r)=5r=35又因?yàn)閐eg(r)=2e=30，而30=35矛盾所以該圖不是平面圖 平面圖基本性質(zhì) abcidefghj14例4：證明彼得森圖是非平面圖證：（1）反證法 平面圖基本15（2）利用定理4:一個(gè)圖是平面圖，當(dāng)且僅當(dāng)它不包含與K33或K5在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子

7、圖。 平面圖基本性質(zhì) bcjdehabcidefghjG的子圖G刪除了egfabcidefghjG與G在2度結(jié)點(diǎn)內(nèi)同構(gòu)abcidehjG”K33彼得森圖不是平面圖，因?yàn)樵搱DG含有1個(gè)子圖G，與K33在2度結(jié)點(diǎn)內(nèi)同構(gòu)。即G與K33具有相同的平面性。15（2）利用定理4:一個(gè)圖是平面圖，當(dāng)且僅當(dāng)它不包含與K316小結(jié)：判定給定圖是否平面圖是否滿足e=3)，若不滿足，則不是平面圖；若滿足e=3v-6，有可能是，也可能不是平面圖（K33），再判斷是否有2度頂點(diǎn)內(nèi)同構(gòu)于K3,3或K5的子圖。 若有則是非平面圖，否則是平面圖。 平面圖基本性質(zhì) 16小結(jié)：判定給定圖是否平面圖是否滿足e=12圖的基本概念路與

8、回路4歐拉圖與漢密爾頓圖平面圖6對偶圖與著色 圖論 3圖的矩陣表示57樹與生成樹12圖的基本概念路與回路4歐拉圖與漢密爾頓圖平面圖6對偶圖與18 圖形著色問題是與平面圖密切相關(guān)的圖論的應(yīng)用問題，該問題最早起源于地圖的著色：一個(gè)地圖中相鄰國家著以不同顏色，那么最小需要多少種顏色？（四色問題）為了敘述圖形的著色的有關(guān)定理，下面先介紹對偶圖的概念，然后再學(xué)習(xí)圖的著色。 對偶圖與著色18 圖形著色問題是與平面圖密切相關(guān)的圖論的應(yīng)用問定義1：給定平面圖G=,它具有面F1,F2,Fn。若存在圖G*=滿足下列條件：1.對于圖G的每一個(gè)面Fi,內(nèi)部有且僅有一個(gè)點(diǎn)vi* V*；2.對于圖G的面Fi,Fj的公共邊

9、界ek,有且僅有一條邊ek*E* 使ek*=(vi*,vj*),且ek與ek*相交；3.當(dāng)且僅當(dāng)ek只是一個(gè)面Fi的邊界時(shí)，vi*存在一個(gè)環(huán)ek*和ek相交。則圖G*為G的對偶圖。v1*v2*v3*e2* e1*e2e1 F1 F2F3 對偶圖與著色定義1：給定平面圖G=,它具有面F1,F2,Fn20定義2：如果圖G的對偶圖G*同構(gòu)于G，則稱G是自對偶圖。例如： 從對偶圖的概念我們可以看到，對于地圖的著色問題可以歸納為對平面圖的頂點(diǎn)的著色問題。 因此，四色問題可以歸結(jié)為：要證明對于任何一個(gè)平面圖，一定可以用四種顏色對它的頂點(diǎn)進(jìn)行著色，使得相鄰的頂點(diǎn)都有不同的顏色。 對偶圖與著色20定義2：如果

10、圖G的對偶圖G*同構(gòu)于G，則稱G是自對偶圖。21定義3：1）圖G的正常著色（著色）是指對G的每個(gè)結(jié)點(diǎn)都指定一種顏色，使得沒有兩個(gè)鄰接的結(jié)點(diǎn)有同一種顏色。2）如果圖G在著色時(shí)，用了n種顏色，則稱G為n-色的。3）對圖G著色時(shí)，需要的最少顏色數(shù)稱作G的著色數(shù)，記作x(G)。 圖的正常著色21定義3： 圖的正常著色221）將圖G中的結(jié)點(diǎn)按度數(shù)的遞減次序排列（可能不唯一）。2）用第一種顏色對第一個(gè)結(jié)點(diǎn)著色，并按順序?qū)εc前面著色點(diǎn) 不鄰接的每一點(diǎn)著上同樣的顏色；3）用第二種顏色對尚未著色的點(diǎn)重復(fù)2），用第三種顏色繼續(xù)， ，直到所有點(diǎn)全部著上色為止。 韋爾奇.鮑威爾（W.P）著色法A1 A2 A3A7 A

11、8A4 A5 A6度數(shù)遞減順序排序：A5，A3，A7，A1，A2，A4，A6，A8221）將圖G中的結(jié)點(diǎn)按度數(shù)的遞減次序排列（可能不唯一）。 23定理1：對于n個(gè)結(jié)點(diǎn)的完全圖Kn，有x(Kn)=n。證明：因?yàn)橥耆珗D中， 每個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)都鄰接，所以n個(gè)結(jié)點(diǎn)的著色數(shù)不能小于n，又n個(gè)結(jié)點(diǎn)的著色數(shù)最多是n，故x(Kn)=n證明：反證法。設(shè)G=，|V|=v,|E|=e，若G中任意結(jié)點(diǎn)vi都有d(vi)=6;則d(vi)=6v; 又由： d(vi)=2e 得:2e=6v, 即e=3v3v-6，故G不是平面圖，與前提矛盾。所以v=3時(shí)，必有一頂點(diǎn)u,使得d(u)=5定理2：設(shè)G為一個(gè)至少有3個(gè)結(jié)點(diǎn)的連

12、通平面圖，則G中必有一個(gè)結(jié)點(diǎn)n，使得d(u)=5。 對偶圖與著色23定理1：對于n個(gè)結(jié)點(diǎn)的完全圖Kn，有x(Kn)=n。證明24定理3：任意平面圖G最多是5色的。證明：1）若v=1,2,3,4,5，顯然成立2）設(shè)v=k時(shí)成立，考察v=k+1時(shí),由定理2可知，必存在結(jié)點(diǎn)u，使d(u)=5，在圖G中刪去u，得到G的子圖：G-u，由歸納假設(shè)知， G-u具有k個(gè)結(jié)點(diǎn)，此時(shí)定理成立?，F(xiàn)將u及其關(guān)聯(lián)邊加入到G-u中，得到原圖G：(1)若d(u)=4，則與u鄰接的結(jié)點(diǎn)不超過4個(gè)，故必可對u正常著色，得到一個(gè)最多5色的圖G；(2)若deg(u)=5，設(shè)與u鄰接的結(jié)點(diǎn)按逆時(shí)針順序排列為v1,v2,v3,v4,v

13、5，它們分別著不同的顏色C1,C2,C3,C4,C5(如果它們著了4顏色，則直接將u著第5種顏色。不需要進(jìn)行下面的分析)設(shè)H1,3為G-u中所有著C1,C3的結(jié)點(diǎn)集，F(xiàn)2,4為著C2,C4的結(jié)點(diǎn)集。 對偶圖與著色 u v2(C2) (C3)v3 (C4) v4 v5(C5) v1(C1) u v2(C2) (C3)v3 (C4) v4 v5(C5) v1(C1) u (C5) v2(C2) (C3)v3 (C4) v4 v1(C1)24定理3：任意平面圖G最多是5色的。證明：1）若v=1,2a)若v1與v3屬于結(jié)點(diǎn)集H1,3所導(dǎo)出子圖的兩個(gè)不同的連通分支，將v1所在分圖中的C1,C3兩種顏色對

14、調(diào)，并不影響G-u的正常著色，然后在u上著C1色，即得到圖G是5色的。 u v2 v3 v4 v5 v1b)若v1與v3屬于結(jié)點(diǎn)集H所導(dǎo)出子圖的同一個(gè)連通分支，從v1到v3必有一條路P，P上所有結(jié)點(diǎn)都著C1或C3色，且P與邊(v3,u)(u,v1)一起構(gòu)成了一條回路L，則L包圍了v2或v4，但不能同時(shí)包圍二者，故v2和v4分別屬于結(jié)集F所導(dǎo)出子圖的兩個(gè)不同連通分支，因此將v2所在分支中C2,C4兩種顏色對調(diào)，并不影響G-u的正常著色，那樣v2與v4都著了C4色， 然后在u上著C2色，即得到圖G是5色的。 u v2 v3 v4 v5 v1a)若v1與v3屬于結(jié)點(diǎn)集H1,3所導(dǎo)出子圖的兩個(gè)不同的連

15、例題：設(shè)G是一個(gè)簡單圖，若G的結(jié)點(diǎn)表示期末考試課程，邊表示關(guān)聯(lián)的兩結(jié)點(diǎn)對應(yīng)的科目不能同一時(shí)間考試。那么，G的一個(gè)適當(dāng)?shù)闹囊饬x是什么？最小著色數(shù)的意義是什么？分析：圖的結(jié)點(diǎn)表示考試課程；相鄰接的兩個(gè)結(jié)點(diǎn)著不同顏色，表示不能同時(shí)考試。即：不鄰接的課程可以同一時(shí)間考試。所以，G的一個(gè)著色表示一張考試安排表。表示如下意義：同一種顏色的結(jié)點(diǎn)表示可以在同一時(shí)間考試的對應(yīng)課程；最小的著色數(shù)表示安排考試時(shí)間的最少次數(shù)。26 對偶圖與著色計(jì)算機(jī)組成原理 計(jì)算機(jī)網(wǎng)絡(luò) 程序設(shè)計(jì)數(shù)據(jù)庫原理 軟件工程離散數(shù)學(xué) 編譯原理 操作系統(tǒng)例題：設(shè)G是一個(gè)簡單圖，若G的結(jié)點(diǎn)表示期末考試課程，邊表示關(guān)例題：某班級(jí)學(xué)生共選修9門課

16、程。期末考試時(shí)，必須提前將這9門課程先考完，每天每人只在下午考一門課程，問：如何確定考完這9門選修課的最少天數(shù)？解：采用無向圖G=表示上述選課及考試關(guān)系。1、構(gòu)造G:V=v1,v2,v3,v9,vi表示課程。S(i)=s | s是該年級(jí)學(xué)生且s選修了課程viE= (vi,vj) | 若S(i) S(j)2、對G進(jìn)行著色。(G)是所需要的最少天數(shù)。27 對偶圖與著色例題：某班級(jí)學(xué)生共選修9門課程。期末考試時(shí)，必須提前將這9門28 對偶圖與著色V1 V2V3V4V6 V5V8V7V9(G)=3所以，按照圖中所示的選課情況下，最少需要3天考完這9門選修課。例題：某班級(jí)學(xué)生共選修9門課程。期末考試時(shí)，

17、必須提前將這9門課程先考完，每天每人只在下午考一門課程，問：如何確定考完這9門選修課的最少天數(shù)？28 對偶圖與著色V1 29 對偶圖與著色例題：將無向完全圖K6的邊隨意涂上紅色或綠色，證明：無論如何涂色，總存在紅色的K3或者綠色的K3。分析：K6的結(jié)點(diǎn)為V=v1, v2, v3, v4, v5, v6，每個(gè)結(jié)點(diǎn)vi關(guān)聯(lián)5條邊。對應(yīng)的鄰接點(diǎn)為v2, v3, v4, v5, v6，在涂色過程中，5條邊中必然存在3條涂同樣顏色的邊，設(shè)都為紅色，3條邊對應(yīng)的結(jié)點(diǎn)為：v2,v3, v4，則另外兩條邊顏色為綠色（也可以紅或者綠）。如果v2, v3, v4構(gòu)成的K3中的1條邊再有1條紅色邊，則必然存在紅色K3。如(v2,v4)涂紅色，則v1,v2,v4為紅色K3，若(v2,v3)涂紅色，則v1,v2,v3為紅色K3，若(v3,v4)涂紅色，則v1,v3,v4為紅色K3。如果v2, v3, v4構(gòu)成的K3中沒有紅色邊，則其本身就是綠色K3。v2v3v4v129 對偶圖與著色例題：將無向完全圖K6的邊隨意涂上紅色或綠30 對偶圖與著色例題：證明