一些特殊的圖

1、第8章 一些特殊的圖 1 二部圖 歐拉圖 哈密爾頓圖 平面圖第8章 一些特殊的圖10/2/2022 7:06 AM28.1二部圖定義：若能將無向圖G=(V,E)的頂點(diǎn)集V劃分成兩個子集V1和V2（V1V2 ）,使得G中任何一條邊的兩個端點(diǎn)一個屬于V1,另一個屬于V2，則稱G為二部圖。若V1中任一頂點(diǎn)與V2中任一頂點(diǎn)均有且僅有一條邊相關(guān)聯(lián)，則稱此二 部圖為完全二部圖。10/2/2022 7:06 AM3定理： 一個無向圖是二部圖當(dāng)且僅當(dāng)G中無奇數(shù)長度的回路。10/2/2022 7:06 AM4匹配二部圖G=(V,E)中, 若ME, 且M中任意兩條邊都沒有公共頂點(diǎn)，則稱M為G中的匹配。極大匹配 若

2、在M中再加入任何1條邊就不是匹配了，則稱為極大匹配。最大匹配 邊數(shù)最多的極大匹配稱為最大匹配 。最大匹配中邊的個數(shù)稱為匹配數(shù)?；拘g(shù)語10/2/2022 7:06 AM5飽和點(diǎn)與非飽和點(diǎn) 屬于匹配M的邊的所有頂點(diǎn)稱為關(guān)于M飽和點(diǎn)，否則稱為M非飽和點(diǎn)。完美匹配 若G中的每個頂點(diǎn)都是M的飽和點(diǎn)，稱M是G的完美匹配。完備匹配 設(shè)V1和V2是二部圖G的互補(bǔ)頂點(diǎn)集，若G中的匹配M使得|M|=min|V1|,|V2|，稱該匹配是完備匹配。10/2/2022 7:06 AM6Hall定理 相異性定理二部圖G = (V1,V2 ,E )， |V1|V2| ，存在從V1到V2的完備匹配 當(dāng)且僅當(dāng)V1中任意k（=

3、1，2，|V1|）個頂點(diǎn)至少連接V2中的k個頂點(diǎn)。t 條件定理10/2/2022 7:06 AM7例：某中學(xué)有3個課外小組：物理組、化學(xué)組、生物組。今有張、王、李、趙、陳5名同學(xué)，若已知：(1)張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員；(2)張為物理組成員，王、李、趙為化學(xué)組成員，王、李、趙、陳為生物組成員；(3)張為物理組和化學(xué)組成員，王、李、趙、陳為生物組成員。問在以上3種情況下能否各選出3名不兼職的組長？ 10/2/2022 7:06 AM8解：設(shè)v1,v2,v3,v4,v5分別表示張、王、李、趙、陳。u1,u2,u3分別表示物理組、化學(xué)組、生物組。在3種情況下

4、作二部圖分別記為G1,G2,G3，如圖所示。10/2/2022 7:06 AM9練習(xí)：在下圖所示的各圖中，是二部圖的為A。在二部圖中存在完美匹配的是B，它們的匹配數(shù)是C。 10/2/2022 7:06 AM10分析無奇數(shù)長度回路的只有圖(3)，(4)，(5)，因而它們都是二部圖；也可根據(jù)定義，直接將兩個頂點(diǎn)集找出，進(jìn)而判斷是否是二部圖。一個圖存在完美匹配的一個必要條件是具有偶數(shù)個頂點(diǎn)，只有圖(4)具有偶數(shù)個頂點(diǎn)，并且它存在完美匹配，匹配數(shù)是3。 10/2/2022 7:06 AM118.2 歐拉圖Konigsberg(哥尼斯堡)七橋問題問題：能否從河岸或小島出發(fā)，通過每一座橋，而且僅僅通過一次

5、就回到原地。10/2/2022 7:06 AM12 Euler(歐拉)1736年對這個問題，給出了否定的回答。將河岸和小島作為圖的頂點(diǎn)，七座橋?yàn)檫?，即可?gòu)成一個無向圖，問題化為圖論中跡(每條邊只走一次)的問題：定義歐拉通路（回路）與歐拉圖： （，）是連通圖，稱經(jīng)過圖中所有邊一次且僅一次的通路（回路）稱為歐拉通路（歐拉回路）。 具有歐拉回路的圖稱為歐拉圖。10/2/2022 7:06 AM13定理1（歐拉定理）：無向圖存在歐拉通路的充要條件是：(1)圖是連通圖；(2)圖中有零個或者兩個奇數(shù)度頂點(diǎn)。若無奇數(shù)度頂點(diǎn)，則通路為回路；若有兩個奇數(shù)度頂點(diǎn)，則它們是每條歐拉通路的端點(diǎn)。10/2/2022 7

6、:06 AM14證明： 必要性： 若存在歐拉通路，且沒有度頂點(diǎn)，則每個頂點(diǎn)都有邊關(guān)聯(lián)，而邊又全在歐拉通路上，故所有頂點(diǎn)都連通。 除了起點(diǎn)，終點(diǎn)外，歐拉通路每經(jīng)過一個頂點(diǎn)，使頂點(diǎn)的度增加，故只有起點(diǎn)和終點(diǎn)才可能成為奇度頂點(diǎn)。據(jù)握手定理的推論，一個奇度頂點(diǎn)是不可能的（兩個都不是或者兩個都是）。 當(dāng)無奇度頂點(diǎn)時，是歐拉回路。充分性： 若(1），(2)成立,構(gòu)造歐拉通路或回路.10/2/2022 7:06 AM15L1: a, c, bL1+L2: a, d, b, a, c, bL2: a, d, b,a10/2/2022 7:06 AM16L1: a, c, bL1+L2: a, d, b, a,

7、 c, bL2: a, d, b,a歐拉通路10/2/2022 7:06 AM17說明： 哥尼斯堡七橋問題，由于四個頂點(diǎn)都是奇度的，不可能有歐拉通路。10/2/2022 7:06 AM18（1）（2）是歐拉圖，（3）是半歐拉圖10/2/2022 7:06 AM19圖(4):歐拉圖 圖(5):不是歐拉圖，亦無歐拉通路。10/2/2022 7:06 AM20例個頂點(diǎn)均為3度，不能一筆畫出 應(yīng)用與推廣：一筆畫圖10/2/2022 7:06 AM21應(yīng)用與推廣：一筆畫圖 10/2/2022 7:06 AM22Hamilton(哈密頓)道路問題： 年發(fā)明的一種游戲。 在一個實(shí)心的正十二面體，20個頂點(diǎn)標(biāo)

8、上世界著名大城市的名字，要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。 這就是“繞行世界”問題。即找一條經(jīng)過所有頂點(diǎn)（城市）一次且只一次的道路（回路）。8.3 哈密頓圖10/2/2022 7:06 AM23（a）正十二面體 （b）哈密頓圖 環(huán)游世界問題圖示10/2/2022 7:06 AM24定義哈密頓路/回路： （，），經(jīng)過圖中所有頂點(diǎn)一次且只一次的通路（回路）稱為哈密頓通路（回路）。 具有哈密頓回路的圖稱為哈密頓圖。 不具有哈密頓回路但具有哈密頓通路的圖稱為半哈密頓圖10/2/2022 7:06 AM25(1)是半哈密頓圖: 存在哈密頓路，不存在哈密頓回路(2)為哈密頓圖:存在哈

9、密頓回路(3)不是哈密頓圖。10/2/2022 7:06 AM26哈密頓圖存在的必要條件定理 設(shè)無向圖G是哈密頓圖，則對于頂點(diǎn)集的每一個真子集V1均有：p(GV1)| V1 |其中， p(G V1)為從G中刪除V1(刪除V1中各頂點(diǎn)及關(guān)聯(lián)的邊)后所得圖的連通分支數(shù)。需注意，定理給出的條件是哈密頓圖的必要條件，不是充分條件，有些圖滿足這個條件，但不是哈密頓圖，例如，彼德森圖。10/2/2022 7:06 AM27| V1 |=3,p(GV1)=4,故p(G- V1)| V1 |不成立。所以此圖不是哈密爾頓圖。例1:10/2/2022 7:06 AM28解：取V1 A1， A2 例2:10/2/2

10、022 7:06 AM29存在3個分支| V1 |=2,p(GV1)=3,故p(G V1)| V1 |不成立。所以此圖不是哈密爾頓圖。10/2/2022 7:06 AM30在彼德森圖中刪除任意一個或兩個頂點(diǎn)，仍是連通的；例3:彼德森圖10/2/2022 7:06 AM31刪除3個頂點(diǎn)，最多只能得到有兩個連通分支的子圖；刪除4個頂點(diǎn)，最多只能得到有3個連通分支的子圖；刪除5個和5個以上的頂點(diǎn)，余下子圖的頂點(diǎn)數(shù)都不大于5，故必不能有5個以上的連通分支數(shù)，所以，滿足p(G V1)| V1 | 。但此圖是典型的非哈密爾頓圖。例3:彼德森圖10/2/2022 7:06 AM32練習(xí)8.13：已只知下列事

11、實(shí)：有7個人a,b,c,d,e,f,g，a：會講英語b：會講英語和華語c：會講英語和意大利語和俄語d：會講日語和華語e：會講德語和意大利語f：會講法語和日語和俄語g：會講法語和德語如何安排座位，才能使每個人都能和他身邊的兩個人交談？10/2/2022 7:06 AM33 G= V=a,b,c,d,e,f,gE=(u,v)|u,v屬于V,u與v有共同語言則將7人排座在圓桌周圍左右能交談在圖G中找哈密頓回路。10/2/2022 7:06 AM34回顧P185:8.210/2/2022 7:06 AM358.4 平面圖定義平面圖：一個圖G如果能以這樣的方式畫在平面上：除頂點(diǎn)處外沒有邊交叉出現(xiàn)，則稱G

12、為平面圖。10/2/2022 7:06 AM3610/2/2022 7:06 AM37設(shè)G是一個連通的平面圖，G的邊將G所在的平面劃分成若干個區(qū)域，每個區(qū)域稱為G的一個面。面積無限的區(qū)域稱為無限面或外部面，常記成R0。面積有限的區(qū)域稱為有限面或內(nèi)部面。包圍每個面的所有邊所構(gòu)成的回路稱為該面的邊界。邊界的長度稱為該面的次數(shù)，R的次數(shù)記為deg(R)。10/2/2022 7:06 AM38R0的邊界為：V1V2V3V4V1 deg (R0)=4R1的邊界為：V1V2V3V4V1 deg (R1)=4R0的邊界為：V1V2V3V6V3V4V1 deg (R0)=6R1的邊界為：V1V2V3V4V5V

13、4V1 deg (R1)=610/2/2022 7:06 AM39R0的邊界為：V1V2V2V3V6V3V5V4V1 deg (R0)=8R1的邊界為：V1V2V3V4V1 deg (R1)=4R2的邊界為：V4V3V5V4 deg (R1)=3R3的邊界為：V2V2 deg (R3)=110/2/2022 7:06 AM40定理 在一個平面圖G中，所有面的次數(shù)之和都等于邊數(shù)m的2倍，即其中，r為面數(shù)。推論 在任何平圖中度為奇數(shù)的面的個數(shù)是偶數(shù)。10/2/2022 7:06 AM41極大平面圖定義8.8 設(shè)G為簡單平面圖，若在G的任意不相鄰的頂點(diǎn)u，v之間加邊(u，v)，所得圖為非平面圖，則稱

14、G為極大平面圖。 K1，K2，K3，K4，,K5-e(K5刪除任意一條邊)都是極大平面圖。 定理 極大平面圖是連通的。 定理 設(shè)G是n(n3)階極大平面圖，則G中不可能存在割點(diǎn)和橋。 定理 設(shè)G為n(n3)階簡單連通的平面圖，G為極大平面圖當(dāng)且僅當(dāng)G的每個面的次數(shù)均為3. 10/2/2022 7:06 AM42連通平面圖的歐拉公式定理 設(shè)G為任意的連通的平面圖，則有 n-m+r=2 成立。其中，n為G中頂點(diǎn)數(shù)， m為邊數(shù)，r為面數(shù)。 (該定理中的公式稱為歐拉公式。)推論1: 設(shè)G是簡單連通平面圖,頂點(diǎn)數(shù)n3時, 邊數(shù)m 3(n-2)推論2: 設(shè)G是簡單連通平面圖,若每個平面由4條或4條以上邊圍

15、成, 則m 2(n-2).10/2/2022 7:06 AM43注意: 歐拉公式和推論1及推論2是判斷一個圖是否平面圖的必要條件.如果一個圖具備這些條件,不一定是平面圖.m= 16, n=8 163*(8-2)但該圖不是平面圖.如果一個圖不具備這些條件,一定不是平面圖.10/2/2022 7:06 AM44利用歐拉公式及推論可證明K5不是平面圖。K5有5個頂點(diǎn)，10條邊， 則3(n-2)= 3(5-2)= 910，與推論1中 m 3(n-2)矛盾的， 因而K5不是平面圖。10/2/2022 7:06 AM45利用歐拉公式及推論可證明K3,3不是平面圖。若K3,3是平面圖，則每個面的次數(shù)至少為4

16、，由推論2： m 2(n-2)因而有9 2(6-2)=8，這是矛盾的，因而K3,3不是平面圖。10/2/2022 7:06 AM46同胚如果兩個圖G1和G2同構(gòu)，或經(jīng)過反復(fù)插入或消去2度頂點(diǎn)后同構(gòu)，則稱G1與G2同胚。插入消去10/2/2022 7:06 AM47同胚著有General Topology一書的數(shù)學(xué)家John L. Kelley曾說：拓?fù)鋵W(xué)家是不知道甜甜圈和咖啡杯的分別的人。10/2/2022 7:06 AM48平面圖的收縮設(shè)e是無向圖G的一條邊. 在G中收縮邊e, 由以下方法給出:當(dāng)e=(u,u)是環(huán)時,刪除邊e; 當(dāng)e=(u,v)是非環(huán)邊時,刪除邊e, 用新的頂點(diǎn)w取代u,v

17、, 并使w除邊e外繼承一切與u、與v的邊關(guān)聯(lián). 在G中收縮邊e得到的圖Ge用表示. 49 平面圖收縮邊e的例子50收縮圖定義設(shè)G是無向圖，在G中收縮邊e稱為G的一個初等收縮。若G經(jīng)一系列的初等收縮得到圖H，則稱H是G的一個收縮圖或說圖G可收到圖H。1930年波蘭數(shù)學(xué)家?guī)炖蟹蛩够?Kuratowski)給出了平面圖的一個判別準(zhǔn)則. 51庫拉圖斯基定理1930一個圖是平面圖當(dāng)且僅當(dāng)它不含與K5同胚的子圖，也不含與K3,3同胚子圖。 瓦格那(K.Wagner)定理1937一個無向圖是平面圖當(dāng)且僅當(dāng)它不含有可收縮到K5或K3,3的子圖。10/2/2022 7:06 AM5210/2/2022 7:0

18、6 AM53練習(xí)8.19：證明如下所示圖G是哈密爾頓圖，但不是平面圖。 解：圖中afbdcea為哈密爾頓回路，見紅邊所示，所以，該圖為哈密爾頓圖。 將圖中邊d，e，e，f，f，d三條去掉，所得圖為原來圖的子圖，它為 K3，3 ，可取V1=a，b，c，V2=d，e，f，由庫拉圖斯基定理可知，該圖不是平面圖。54練習(xí)：8.23558.23 解：6 個頂點(diǎn)11條邊的非平面圖。（子圖與K3,3或K5同胚）K3,3 ：6個頂點(diǎn)9條邊K5 ： 5個頂點(diǎn)10條邊 K3,3加2條邊的圖:56K5加1個頂點(diǎn)，1條邊的圖：57對偶圖 與著色設(shè)平面圖G，有r個面，v個頂點(diǎn)，e條邊，構(gòu)造G的對偶圖G*如下：1.在G的每個面中任取一點(diǎn)作為G*的頂點(diǎn)。2.對G中每條邊，如果邊是兩個面的公共邊界，則連接兩個面中對應(yīng)頂點(diǎn)所得的邊為G*的邊；如果G中邊只是一個面的邊界，則以該面中頂點(diǎn)做與此邊相交的環(huán)，該環(huán)亦為 G*的邊。這樣所得的圖為G的對偶圖.10/2/2022 7:06 AM5810/2/2022 7:06 AM5910/2/2022 7:06 AM60 圖中，兩個藍(lán)邊圖是同構(gòu)的，但它們的對偶圖(紅邊圖