圖的基本概念與握手定理

1、1第三部分第三部分 圖圖 論論 第一講 圖論的基本概念與握手定理2一、一、 圖的概念圖的概念 二、二、 圖的類型圖的類型三、三、 結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的度數(shù)四、四、 握手定理握手定理五、五、 同構(gòu)概念同構(gòu)概念六、六、 鄰接矩陣鄰接矩陣主要內(nèi)容主要內(nèi)容3圖論研究圖論研究圖的邏輯結(jié)構(gòu)與性質(zhì)圖的邏輯結(jié)構(gòu)與性質(zhì).引引 言言 圖論最早起源于一些數(shù)字游戲的難題研究圖論的最早論文是1736年瑞士數(shù)學(xué)家歐拉（Leonhard Euler）所寫，從而使歐拉成為圖論的創(chuàng)始人。 圖論是組合數(shù)學(xué)的一個(gè)分支，圖論是組合數(shù)學(xué)的一個(gè)分支，研究集合上的二研究集合上的二元關(guān)系的工具，是建立數(shù)學(xué)模型的一個(gè)重要手段。元關(guān)系的工具，是建立

2、數(shù)學(xué)模型的一個(gè)重要手段。在物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)等各方面都取得在物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)等各方面都取得了豐碩的成果。計(jì)算機(jī)的迅速發(fā)展，使得圖論成了豐碩的成果。計(jì)算機(jī)的迅速發(fā)展，使得圖論成為數(shù)學(xué)領(lǐng)域里發(fā)展最快的分支之一。為數(shù)學(xué)領(lǐng)域里發(fā)展最快的分支之一。4引引 言言哥尼斯堡七橋問題哥尼斯堡七橋問題 當(dāng)時(shí)哥尼斯堡（Konigsberg）城（現(xiàn)名加里寧格勒,屬俄羅斯）的居民有郊游的習(xí)慣，在城郊的普雷格爾（Pregel）河畔，河中有兩個(gè)小島，七座橋?qū)蓚€(gè)小島和河岸連接起來，如圖所示，問一個(gè)人能否從任一小島出發(fā)不重復(fù)地走遍七座小橋？ 51852年畢業(yè)于倫敦大學(xué)的弗年畢業(yè)于倫敦大學(xué)的弗南西斯南西斯格思

3、里發(fā)現(xiàn)了一種有格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：趣的現(xiàn)象：“看來，每幅地看來，每幅地圖都可以用四種顏色著色，圖都可以用四種顏色著色，使得有共同邊界的國(guó)家都被使得有共同邊界的國(guó)家都被著上不同的顏色。著上不同的顏色。”這個(gè)現(xiàn)這個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？證明呢？四色問題四色問題6Hamilton問題問題 1856年，英國(guó)數(shù)學(xué)家年，英國(guó)數(shù)學(xué)家Hamilton設(shè)計(jì)了一個(gè)名為周游世設(shè)計(jì)了一個(gè)名為周游世界的游戲：他用一個(gè)正十二面體的二十個(gè)端點(diǎn)表示世界上的界的游戲：他用一個(gè)正十二面體的二十個(gè)端點(diǎn)表示世界上的二十座大城市（見圖），提出的問題是要求游戲者找一條沿二十座大城市（見圖），提

4、出的問題是要求游戲者找一條沿著十二面體的棱通過每個(gè)端點(diǎn)恰好一次的行走路線。著十二面體的棱通過每個(gè)端點(diǎn)恰好一次的行走路線。此路線稱為：此路線稱為：哈密爾頓回路哈密爾頓回路， 而此圖稱為：而此圖稱為：哈密爾頓圖哈密爾頓圖。7圖圖G = , 其中其中(1) V 為頂點(diǎn)集，為頂點(diǎn)集，其元素稱為其元素稱為結(jié)點(diǎn)（頂點(diǎn)）結(jié)點(diǎn)（頂點(diǎn)）-用來表示事物用來表示事物(2) E為為V V 的多重集。的多重集。其元素稱為其元素稱為邊邊-表示事物表示事物間的二元關(guān)系間的二元關(guān)系( (一一) ) 圖的定義圖的定義: :一、圖的概念一、圖的概念8( (二二) ) 結(jié)點(diǎn)與邊的關(guān)系結(jié)點(diǎn)與邊的關(guān)系: : 結(jié)點(diǎn)與邊結(jié)點(diǎn)與邊(不不)相

5、相 關(guān)聯(lián)關(guān)聯(lián)： 結(jié)點(diǎn)與結(jié)點(diǎn)結(jié)點(diǎn)與結(jié)點(diǎn), ,邊與邊邊與邊( (不不) )相相鄰接鄰接一、圖的概念一、圖的概念( (三三) ) 特殊點(diǎn)特殊點(diǎn)孤立點(diǎn): 不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)懸掛點(diǎn): 只與一條邊相關(guān)聯(lián)的結(jié)點(diǎn) ( (四四) ) 特殊的邊特殊的邊: :環(huán): 一條邊若與兩個(gè)相同的結(jié)點(diǎn)相關(guān)聯(lián)則稱為環(huán)。多重邊(平行邊）:與兩個(gè)結(jié)點(diǎn)相關(guān)聯(lián)的邊若多于一條，則稱這些邊為多重邊。 9有向圖與無向圖:簡(jiǎn)單圖與多重圖:簡(jiǎn)單圖-不含環(huán)與多重邊；多重圖-含多重邊有權(quán)圖與無權(quán)圖:b.按邊的種類分類：按邊的種類分類：有限圖與無限圖：V與E為有限集合的圖叫有限圖，否則叫無限圖。(n,m)圖：有 n 個(gè)結(jié)點(diǎn)與 m 條邊的圖。 零圖

6、: 即(n,0)圖; 平凡圖: 即(1,0)圖。完全圖:任意兩個(gè)結(jié)點(diǎn)都相鄰接的圖。K-正則圖:每個(gè)結(jié)點(diǎn)都與K條邊相關(guān)聯(lián)。c. c. 按結(jié)點(diǎn)集與邊集的按結(jié)點(diǎn)集與邊集的“階階”分類分類a a 按邊的方向分類按邊的方向分類二、二、 圖的類型圖的類型10注意注意：完全圖是完全圖是 n n- -1 1 正則圖正則圖完全圖的每個(gè)結(jié)點(diǎn)都與其它 n-1 個(gè)結(jié)點(diǎn)相鄰接,即與n-1條邊相關(guān)聯(lián),所以是n-1正則圖,反之正則圖不一定是完全圖。1.完全圖： 2.正則圖： 是3正則圖 完全圖, 不是完全圖二、二、 圖的類型圖的類型11子圖：子圖： 設(shè)設(shè)G=, G=為兩個(gè)圖，滿足為兩個(gè)圖，滿足V V且且E E，則稱，則稱G

7、為為G的的子圖子圖， G為為G的的母圖母圖，記，記作作G G。(1)(1)GG為為G G的的真子圖：真子圖：若若GG G G且且VV V V或或EE E E。 (2)G為為G的的生成子圖：生成子圖：若若GG G G且且VV = = V V。(3)V(3)V1 1導(dǎo)出的導(dǎo)出子圖：導(dǎo)出的導(dǎo)出子圖：頂點(diǎn)集頂點(diǎn)集VV1 1 V V, ,邊集為邊集為兩端點(diǎn)均在兩端點(diǎn)均在V V1 1中的全體邊構(gòu)成的子圖。中的全體邊構(gòu)成的子圖。(4) E E1 1導(dǎo)出的導(dǎo)出子圖：導(dǎo)出的導(dǎo)出子圖：EE1 1 E,E,以以E E1 1中邊關(guān)聯(lián)的中邊關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的頂點(diǎn)的全體為頂點(diǎn)集的G G的子圖。的子圖。二、二、 圖

8、的類型圖的類型12abcda1b1abcdd1a1b1c1abcdd1b1abcdd1a1b1c1母母圖圖真子圖真子圖V V或或E E生成子圖生成子圖G G且且V=V導(dǎo)出子圖導(dǎo)出子圖V V或或E E二、二、 圖的類型圖的類型13補(bǔ)補(bǔ) 圖圖 設(shè)G =V, E, 對(duì)于 G1 =V, E1 若有 G2 =V, EE1是完全圖, 且 EE1 = , 則稱G1 是 G 的補(bǔ)圖。 圖G 圖G1 圖G2二、二、 圖的類型圖的類型14 在無向圖在無向圖G中，與中，與v相鄰的頂點(diǎn)的數(shù)目稱為相鄰的頂點(diǎn)的數(shù)目稱為v的的次或度次或度/degree。記為記為deg(v)或或d(v)。 在有向圖在有向圖G中，以中，以v為

9、終點(diǎn)的邊的條數(shù)稱為為終點(diǎn)的邊的條數(shù)稱為v的的入次或入度入次或入度/in-degree。記為。記為deg(v)或或d (v)。以。以v為起點(diǎn)的邊的條數(shù)稱為為起點(diǎn)的邊的條數(shù)稱為v的的出次或出度出次或出度/out-degree。記為記為deg+(v)或或d +(v)。三、三、 結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的度數(shù)15在無向圖在無向圖G G中中, ,令令 (G)=maxd(v)|vV(G(G)=maxd(v)|vV(G) (G)= mind(v)| vV(G(G)= mind(v)| vV(G) ) 稱稱(G)(G)和和 (G)(G)分別為分別為G G的最大度和最小度。的最大度和最小度。在有向圖在有向圖D D中中,

10、,類似定義類似定義(D)(D)、 (G)(G)。另外。另外, ,令令 + +(G) = maxd(G) = maxd+ +(v)| vV(D(v)| vV(D) ) + +(G) = mind(G) = mind+ +(v)| vV(D(v)| vV(D) ) - -(G) = maxd(G) = maxd- -(v)| vV(D(v)| vV(D) ) - -(G) = mind(G) = mind- -(v)| vV(D(v)| vV(D) ) 分別為分別為D D的最大出度、最小出度、最大入度、最小的最大出度、最小出度、最大入度、最小入度。簡(jiǎn)記作入度。簡(jiǎn)記作、 、 + +、 + + 、 -

11、 - 、 - - 。三、三、 結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的度數(shù)16mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理1 設(shè)設(shè)G=為為任意無向圖任意無向圖，V=v1,v2,vn, |E|=m, 則則四、握手定理四、握手定理定理定理2 設(shè)設(shè)D=為為任意有向圖任意有向圖，V=v1,v2,vn, |E|=m, 則則證證 G中每條邊中每條邊 (包括環(huán)包括環(huán)) 均有兩個(gè)端點(diǎn)，所以在計(jì)算均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供度數(shù)之和時(shí)，每條邊均提供2度，度，m 條邊共提供條邊共提供 2m 度度.17握手定理推論及應(yīng)用握手定理推論及應(yīng)用推論推論 任何圖

12、任何圖 (無向或有向無向或有向) 中，奇度頂點(diǎn)的個(gè)數(shù)是中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)偶數(shù).例例1 無向圖無向圖G有有16條邊，條邊，3個(gè)個(gè)4度頂點(diǎn)，度頂點(diǎn)，4個(gè)個(gè)3度頂度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于點(diǎn)，其余頂點(diǎn)度數(shù)均小于3，問，問G的階數(shù)的階數(shù)n為幾？為幾？解解 設(shè)除設(shè)除3度與度與4度頂點(diǎn)外，還有度頂點(diǎn)外，還有x個(gè)頂點(diǎn)個(gè)頂點(diǎn)v1, v2, , vx， 則則 d(vi) 2，i =1, 2, , x，于是于是 32 24+2x得得 x 4, 階數(shù)階數(shù) n 4+4+3=11. 18五、圖的同構(gòu)五、圖的同構(gòu)定義定義 設(shè)設(shè)G1=, G2=為兩個(gè)圖為兩個(gè)圖(有向或有向或無向圖無向圖)，（1）若存在雙射函數(shù)）若存在

13、雙射函數(shù)f:V1V2, 對(duì)于對(duì)于vi,vj V1, (vi,vj) E1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) (f(vi),f(vj) E2 （ E1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) E2 )（2）(vi,vj)（）與）與 (f(vi),f(vj)（）的重?cái)?shù)相同。的重?cái)?shù)相同。則稱則稱G1與與G2是是同構(gòu)同構(gòu)的，記作的，記作G1 G2. 19圖同構(gòu)的必要條件圖同構(gòu)的必要條件l 圖之間的同構(gòu)關(guān)系是等價(jià)關(guān)系圖之間的同構(gòu)關(guān)系是等價(jià)關(guān)系.l 同構(gòu)的必要條件：同構(gòu)的必要條件： 邊數(shù)相同，頂點(diǎn)數(shù)相同邊數(shù)相同，頂點(diǎn)數(shù)相同; 度數(shù)列相同度數(shù)列相同; 度數(shù)相同的結(jié)點(diǎn)數(shù)目相同度數(shù)相同的結(jié)點(diǎn)數(shù)目相同20圖同構(gòu)的實(shí)例圖同構(gòu)的實(shí)例 (1) (2) (3

14、) (4) 圖中，圖中，(1)與與(2)不同構(gòu)（度數(shù)列不同），不同構(gòu)（度數(shù)列不同），(3)與與(4)也不同構(gòu)也不同構(gòu).adcb無向圖b (c)a (b)c (a)d21定定義義 鄰鄰接接矩矩陣陣： 設(shè)設(shè)有有向向圖圖 （， ） ， 1 1， 2 2，n n ，若若用用方方陣陣nnijaA)(來來表表示示，其其中中 EVVEVVajijiij),(0),(1 稱稱為為的的鄰鄰接接矩矩陣陣。六、圖的表示六、圖的表示鄰接矩陣鄰接矩陣22同構(gòu)判定算法（用鄰接矩陣）同構(gòu)判定算法（用鄰接矩陣）1、根據(jù)圖確定其鄰接矩陣、根據(jù)圖確定其鄰接矩陣2、計(jì)算行次（矩陣每行的個(gè)數(shù)、計(jì)算行次（矩陣每行的個(gè)數(shù)-對(duì)應(yīng)于出次）對(duì)應(yīng)于出次）