1、離散數(shù)學(xué)離散數(shù)學(xué)教案教案計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程學(xué)時(shí)：課程學(xué)時(shí)：64主主 講：宋講：宋 成成河南理工大學(xué)河南理工大學(xué)電子教案電子教案 圖論是最近幾年發(fā)展迅速而又應(yīng)用廣泛的一圖論是最近幾年發(fā)展迅速而又應(yīng)用廣泛的一門(mén)新興科學(xué)。圖論是一個(gè)重要的數(shù)學(xué)分支。它門(mén)新興科學(xué)。圖論是一個(gè)重要的數(shù)學(xué)分支。它最早起源一些數(shù)學(xué)游戲的難題研究，數(shù)學(xué)家歐最早起源一些數(shù)學(xué)游戲的難題研究，數(shù)學(xué)家歐拉拉1736年發(fā)表了關(guān)于圖論的第一篇論文，解決年發(fā)表了關(guān)于圖論的第一篇論文，解決了著名的哥尼斯堡七橋問(wèn)題?？讼；舴?qū)﹄娐妨酥母缒崴贡て邩騿?wèn)題。克?；舴?qū)﹄娐肪W(wǎng)絡(luò)的研究、凱來(lái)在有機(jī)化學(xué)的計(jì)算中都應(yīng)用網(wǎng)絡(luò)的研究

2、、凱來(lái)在有機(jī)化學(xué)的計(jì)算中都應(yīng)用了樹(shù)和生成樹(shù)的概念。以及在民間廣為流傳的了樹(shù)和生成樹(shù)的概念。以及在民間廣為流傳的一些游戲問(wèn)題：例如迷宮問(wèn)題、棋盤(pán)上馬的行一些游戲問(wèn)題：例如迷宮問(wèn)題、棋盤(pán)上馬的行走路線問(wèn)題等等。這些古老的問(wèn)題當(dāng)時(shí)吸引了走路線問(wèn)題等等。這些古老的問(wèn)題當(dāng)時(shí)吸引了許多學(xué)者的注意，從而在這些問(wèn)題研究的基礎(chǔ)許多學(xué)者的注意，從而在這些問(wèn)題研究的基礎(chǔ)上，又提出了著名的四色猜想和環(huán)游世界各國(guó)上，又提出了著名的四色猜想和環(huán)游世界各國(guó)的問(wèn)題的問(wèn)題第四篇：圖論第四篇：圖論第四篇篇：圖論第四篇篇：圖論 圖論的不斷發(fā)展，他在解決運(yùn)籌學(xué)、網(wǎng)絡(luò)理圖論的不斷發(fā)展，他在解決運(yùn)籌學(xué)、網(wǎng)絡(luò)理論、信息論、控制論、博弈論以

3、及計(jì)算機(jī)科學(xué)論、信息論、控制論、博弈論以及計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域的問(wèn)題時(shí)，顯示出越來(lái)越大的效果等各個(gè)領(lǐng)域的問(wèn)題時(shí)，顯示出越來(lái)越大的效果 對(duì)于這樣一門(mén)應(yīng)用廣泛的學(xué)科，其包含的內(nèi)對(duì)于這樣一門(mén)應(yīng)用廣泛的學(xué)科，其包含的內(nèi)容是豐富的，本篇首先給出圖、簡(jiǎn)單圖、完全容是豐富的，本篇首先給出圖、簡(jiǎn)單圖、完全圖、子圖、路和圖的同構(gòu)等概念，接著研究了圖、子圖、路和圖的同構(gòu)等概念，接著研究了連通圖性質(zhì)和規(guī)律，給出了鄰接矩陣、可達(dá)性連通圖性質(zhì)和規(guī)律，給出了鄰接矩陣、可達(dá)性矩陣、連通矩陣和完全關(guān)聯(lián)矩陣的定義。最后矩陣、連通矩陣和完全關(guān)聯(lián)矩陣的定義。最后介紹了歐拉圖與哈密爾頓圖、平面圖、對(duì)偶圖介紹了歐拉圖與哈密爾頓圖、平面

4、圖、對(duì)偶圖與著色、樹(shù)與生成樹(shù)與著色、樹(shù)與生成樹(shù)。為今后有關(guān)學(xué)科及課程為今后有關(guān)學(xué)科及課程的學(xué)習(xí)和研究提供方便的學(xué)習(xí)和研究提供方便第七章：圖論第七章：圖論7.1 圖的基本概念圖的基本概念7.2 路與回路路與回路7.3 圖的矩陣表示圖的矩陣表示7.4 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖7.5 平面圖平面圖7.6 對(duì)偶圖和著色對(duì)偶圖和著色 7.7 樹(shù)與生成樹(shù)樹(shù)與生成樹(shù)第七章：圖論第七章：圖論教學(xué)目的及要求：教學(xué)目的及要求： 深刻理解和掌握?qǐng)D的有關(guān)概念和表示深刻理解和掌握?qǐng)D的有關(guān)概念和表示教學(xué)類(lèi)容：教學(xué)類(lèi)容： 圖的基本概念、路與回路、圖的矩陣表示、歐拉圖圖的基本概念、路與回路、圖的矩陣表示、歐拉圖與

5、漢密爾頓圖、平面圖、對(duì)偶圖與著色、樹(shù)與生與漢密爾頓圖、平面圖、對(duì)偶圖與著色、樹(shù)與生成樹(shù)。成樹(shù)。教學(xué)重點(diǎn)：教學(xué)重點(diǎn)： 圖、路、圖的矩陣表示、平面圖、對(duì)偶圖與著色、圖、路、圖的矩陣表示、平面圖、對(duì)偶圖與著色、樹(shù)與生成樹(shù)樹(shù)與生成樹(shù)教學(xué)難點(diǎn)：教學(xué)難點(diǎn)： 樹(shù)與生成樹(shù)。樹(shù)與生成樹(shù)。第七章：圖論第七章：圖論7.1 圖的基本概念圖的基本概念 7.1.1圖圖 兩個(gè)個(gè)體兩個(gè)個(gè)體x，y的無(wú)序序列稱(chēng)為無(wú)序?qū)?，記為的無(wú)序序列稱(chēng)為無(wú)序?qū)?，記?x,y)。在無(wú)序?qū)?。在無(wú)序?qū)?x,y)中，中，x，y是無(wú)序的，它們的是無(wú)序的，它們的順序可以顛倒，即順序可以顛倒，即(x,y)=(y,x)?！径x【定義7.1.1】 圖圖G是一個(gè)三

6、重組是一個(gè)三重組 V(G),E(G), G 其中：其中：V(G)是非空結(jié)點(diǎn)集。是非空結(jié)點(diǎn)集。 E(G)是邊集。是邊集。 G是邊集到結(jié)點(diǎn)的有序?qū)蚴沁吋浇Y(jié)點(diǎn)的有序?qū)?無(wú)序?qū)系暮瘮?shù)。無(wú)序?qū)系暮瘮?shù)。第七章：圖論第七章：圖論【例【例7.1】G= V(G),E(G), G 其中：其中：V(G)= a,b,c,d E(G)= e1,e2,e3,e4 G： G(e1)=(a,b) G(e2)=(b,c) G(e3)=(a,c) G(e4)=(a,a)試畫(huà)出試畫(huà)出G的圖形。的圖形。 解：解：G的圖形如圖的圖形如圖7.1所示所示。第七章：圖論第七章：圖論 由于在不引起混亂的情況下，圖的邊可以用有由于

7、在不引起混亂的情況下，圖的邊可以用有序?qū)驘o(wú)序?qū)χ苯颖硎尽Ｒ虼耍瑘D可以簡(jiǎn)單的表示序?qū)驘o(wú)序?qū)χ苯颖硎?。因此，圖可以簡(jiǎn)單的表示為：為： G= V,E 其中：其中：V是非空的結(jié)點(diǎn)集。是非空的結(jié)點(diǎn)集。 E是邊的有序?qū)驘o(wú)序?qū)M成的集合。是邊的有序?qū)驘o(wú)序?qū)M成的集合。 按照這種表示法，按照這種表示法，例例7.1中的圖可以簡(jiǎn)記為：中的圖可以簡(jiǎn)記為： G= V,E 其中：其中：V= a,b,c,d E= (a,b), (b,c), (a,c), (a,a) 第七章：圖論第七章：圖論【定義【定義7.1.2 】 若圖若圖G有有n個(gè)結(jié)點(diǎn)，則稱(chēng)該圖為個(gè)結(jié)點(diǎn)，則稱(chēng)該圖為n階圖。階圖?！径x【定義7.1.3】 設(shè)設(shè)

8、G為圖，如果為圖，如果G的所有邊都是有向邊，則的所有邊都是有向邊，則稱(chēng)稱(chēng)G為有向圖。如果為有向圖。如果G的所有邊都是無(wú)向邊，則稱(chēng)的所有邊都是無(wú)向邊，則稱(chēng)G為無(wú)向?yàn)闊o(wú)向圖。如果圖。如果G中既有有向邊，又有無(wú)向邊，則稱(chēng)中既有有向邊，又有無(wú)向邊，則稱(chēng)G為混合圖。為混合圖。 圖圖7.2的的(a)是無(wú)向圖，是無(wú)向圖，(b)是有向圖，是有向圖，(c)是混合圖。是混合圖。 第七章：圖論第七章：圖論 在一個(gè)圖中，若兩個(gè)結(jié)點(diǎn)由一條邊在一個(gè)圖中，若兩個(gè)結(jié)點(diǎn)由一條邊(有向邊或無(wú)向邊有向邊或無(wú)向邊)關(guān)聯(lián)，則稱(chēng)其中的一個(gè)結(jié)點(diǎn)是另一個(gè)結(jié)點(diǎn)的鄰接點(diǎn)。并稱(chēng)關(guān)聯(lián)，則稱(chēng)其中的一個(gè)結(jié)點(diǎn)是另一個(gè)結(jié)點(diǎn)的鄰接點(diǎn)。并稱(chēng)這兩個(gè)結(jié)點(diǎn)相互鄰接。

9、這兩個(gè)結(jié)點(diǎn)相互鄰接。 在一個(gè)圖中不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)，稱(chēng)為孤立點(diǎn)。在一個(gè)圖中不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)，稱(chēng)為孤立點(diǎn)。 在一個(gè)圖中，如果兩條邊關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)，則稱(chēng)其在一個(gè)圖中，如果兩條邊關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)，則稱(chēng)其中的一個(gè)邊是另一個(gè)邊的鄰接邊。并稱(chēng)這兩個(gè)邊相互鄰接。中的一個(gè)邊是另一個(gè)邊的鄰接邊。并稱(chēng)這兩個(gè)邊相互鄰接。關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的一條邊叫做環(huán)或自回路。在有向圖中關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的一條邊叫做環(huán)或自回路。在有向圖中環(huán)的方向可以是順時(shí)針，也可以是逆時(shí)針，它們是等效的。環(huán)的方向可以是順時(shí)針，也可以是逆時(shí)針，它們是等效的。【定義【定義7.1.4】 由孤立點(diǎn)組成的圖叫做零圖。由一個(gè)孤立由孤立點(diǎn)組成的圖叫

10、做零圖。由一個(gè)孤立點(diǎn)組成的圖叫做平凡圖。點(diǎn)組成的圖叫做平凡圖。 根據(jù)根據(jù)定義定義7.1.4，平凡圖一定是零圖。平凡圖一定是零圖。 第七章：圖論第七章：圖論7.1.2結(jié)點(diǎn)的度及其性質(zhì)結(jié)點(diǎn)的度及其性質(zhì)【定義【定義7.1.5】設(shè)設(shè)G= V,E 是圖，是圖，v V，與，與v相關(guān)聯(lián)相關(guān)聯(lián)的邊數(shù)叫做結(jié)點(diǎn)的邊數(shù)叫做結(jié)點(diǎn)v的度。記為的度。記為deg(v)。規(guī)定，自回。規(guī)定，自回路為所在結(jié)點(diǎn)增加路為所在結(jié)點(diǎn)增加2度。度。 在圖在圖G= V,E 中，度數(shù)最大中，度數(shù)最大(小小)的結(jié)點(diǎn)的度的結(jié)點(diǎn)的度叫做圖叫做圖G的最大的最大(小小)度，記為度，記為 (G)( (G)。圖。圖G的的最大度和最小度表示為：最大度和最小度

11、表示為： (G)=max deg(v) | v V (G)= min deg(v) | v V 在圖在圖7.1中，中， (G)=4， (G)=0。 第七章：圖論第七章：圖論【定理【定理7.1.1】在任何圖在任何圖G= V,E 中，所有結(jié)點(diǎn)度中，所有結(jié)點(diǎn)度數(shù)的和等于邊數(shù)的數(shù)的和等于邊數(shù)的2倍。即：倍。即：= 2|E| 證明：證明：圖的每一條邊都和兩個(gè)結(jié)點(diǎn)相關(guān)聯(lián)，圖的每一條邊都和兩個(gè)結(jié)點(diǎn)相關(guān)聯(lián)，為每個(gè)相關(guān)聯(lián)的結(jié)點(diǎn)增加一度為每個(gè)相關(guān)聯(lián)的結(jié)點(diǎn)增加一度, 給圖增加兩度。給圖增加兩度。所以所有結(jié)點(diǎn)度數(shù)的和等于邊數(shù)的所以所有結(jié)點(diǎn)度數(shù)的和等于邊數(shù)的2倍。倍。 推論推論 在任何圖在任何圖G= V,E 中，度數(shù)為

12、奇數(shù)的中，度數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。結(jié)點(diǎn)必為偶數(shù)個(gè)。第七章：圖論第七章：圖論【定義【定義7.1.6】設(shè)設(shè)G= V,E 是有向圖，是有向圖，v V，射入，射入(出出)結(jié)點(diǎn)結(jié)點(diǎn)v的邊數(shù)稱(chēng)為結(jié)點(diǎn)的邊數(shù)稱(chēng)為結(jié)點(diǎn)v的入的入(出出)度。記為度。記為deg(v) (deg(v)。 顯然，任何結(jié)點(diǎn)的入度與出度的和等于該結(jié)顯然，任何結(jié)點(diǎn)的入度與出度的和等于該結(jié)點(diǎn)的度數(shù)，即點(diǎn)的度數(shù)，即deg(v)=deg(v)+deg(v)?！径ɡ怼径ɡ?.1.2】在有向圖中，所有結(jié)點(diǎn)入度的和等在有向圖中，所有結(jié)點(diǎn)入度的和等于所有結(jié)點(diǎn)出度的和。于所有結(jié)點(diǎn)出度的和。 證明：證明：在有向圖中每一條邊對(duì)應(yīng)一個(gè)入度和在有向圖中每一條邊

13、對(duì)應(yīng)一個(gè)入度和一個(gè)出度，為圖的入度和出度各增加一個(gè)出度，為圖的入度和出度各增加1。所以，。所以，所有結(jié)點(diǎn)入度的和等于邊數(shù)，所有結(jié)點(diǎn)出度的和所有結(jié)點(diǎn)入度的和等于邊數(shù)，所有結(jié)點(diǎn)出度的和也等于邊數(shù)。也等于邊數(shù)。 第七章：圖論第七章：圖論7.1.3多重圖、簡(jiǎn)單圖、完全圖和正則圖多重圖、簡(jiǎn)單圖、完全圖和正則圖【定義【定義7.1.7 】 在圖在圖G中，連接同一對(duì)結(jié)點(diǎn)的多條相中，連接同一對(duì)結(jié)點(diǎn)的多條相同邊稱(chēng)為平行邊。平行邊的條數(shù)稱(chēng)為該平行邊的重?cái)?shù)。同邊稱(chēng)為平行邊。平行邊的條數(shù)稱(chēng)為該平行邊的重?cái)?shù)。含平行邊的圖叫多重圖。不含平行邊和環(huán)的圖叫簡(jiǎn)單含平行邊的圖叫多重圖。不含平行邊和環(huán)的圖叫簡(jiǎn)單圖。圖。 例如，在圖例

14、如，在圖7.3(a)中結(jié)點(diǎn)中結(jié)點(diǎn)a和和b之間有兩條平行邊，之間有兩條平行邊，結(jié)點(diǎn)結(jié)點(diǎn)b和和c之間有三條平行邊，結(jié)點(diǎn)之間有三條平行邊，結(jié)點(diǎn)b上有兩條平行邊，上有兩條平行邊，這兩條平行邊都是環(huán)。圖這兩條平行邊都是環(huán)。圖7.3(a)不是簡(jiǎn)單圖。不是簡(jiǎn)單圖。 又如，在圖又如，在圖7.3(b)中結(jié)點(diǎn)中結(jié)點(diǎn)v1和和v2之間有兩條平行之間有兩條平行邊。邊。v2和和v3之間的兩條邊，因?yàn)榉较虿煌?，所以不是之間的兩條邊，因?yàn)榉较虿煌圆皇瞧叫羞?。圖平行邊。圖7.3(b)不是簡(jiǎn)單圖。不是簡(jiǎn)單圖。 簡(jiǎn)單圖不含平行邊和環(huán)。簡(jiǎn)單圖不含平行邊和環(huán)。 第七章：圖論第七章：圖論第七章：圖論第七章：圖論【定理【定理7.1.

15、3 】 設(shè)設(shè)G為為n階簡(jiǎn)單無(wú)向圖，則階簡(jiǎn)單無(wú)向圖，則 (G)n1。 證明：證明：因?yàn)橐驗(yàn)镚有有n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，G的任何結(jié)點(diǎn)的任何結(jié)點(diǎn)v最多只能最多只能與其余的與其余的n1結(jié)點(diǎn)相鄰接；又因?yàn)榻Y(jié)點(diǎn)相鄰接；又因?yàn)镚為簡(jiǎn)單圖，既無(wú)平為簡(jiǎn)單圖，既無(wú)平行邊，又無(wú)環(huán)。所以行邊，又無(wú)環(huán)。所以deg(v)n1。由。由v的任意性，就有的任意性，就有 (G) =max deg(v) | v V n1。【定義【定義7.1.8 】 設(shè)設(shè)G為為n階簡(jiǎn)單無(wú)向圖，若階簡(jiǎn)單無(wú)向圖，若G中的每個(gè)結(jié)中的每個(gè)結(jié)點(diǎn)都與其余的點(diǎn)都與其余的n1個(gè)結(jié)點(diǎn)相鄰接，則稱(chēng)個(gè)結(jié)點(diǎn)相鄰接，則稱(chēng)G為為n階無(wú)向完階無(wú)向完全圖。記為全圖。記為Kn。在。在n

16、階無(wú)向完全圖中，給每一條邊任意階無(wú)向完全圖中，給每一條邊任意確定一個(gè)方向，所得到的圖稱(chēng)為確定一個(gè)方向，所得到的圖稱(chēng)為n階有向完全圖。也記階有向完全圖。也記為為Kn。 今后，將今后，將n階無(wú)向完全圖和階無(wú)向完全圖和n階有向完全圖統(tǒng)稱(chēng)為階有向完全圖統(tǒng)稱(chēng)為n階完全圖。階完全圖。 第七章：圖論第七章：圖論【定理【定理7.1.4】 n階完全圖階完全圖Kn的邊數(shù)為的邊數(shù)為 證明：證明：在在Kn中，每個(gè)結(jié)點(diǎn)都與其余的中，每個(gè)結(jié)點(diǎn)都與其余的n1結(jié)點(diǎn)結(jié)點(diǎn)相鄰接，即任何一對(duì)結(jié)點(diǎn)之間都有一條邊，故邊數(shù)相鄰接，即任何一對(duì)結(jié)點(diǎn)之間都有一條邊，故邊數(shù)應(yīng)為應(yīng)為 【定義【定義7.1.9 】設(shè)設(shè)G為為n階簡(jiǎn)單無(wú)向圖，若階簡(jiǎn)單無(wú)

17、向圖，若G中每個(gè)結(jié)中每個(gè)結(jié)點(diǎn)都是點(diǎn)都是k度的，則稱(chēng)度的，則稱(chēng)G為為k次正則圖。次正則圖。 ) 1(212nnCn) 1(212nnCn第七章：圖論第七章：圖論7.1.4圖的同構(gòu)圖的同構(gòu) 在圖論中只關(guān)心結(jié)點(diǎn)間是否有連線，而不關(guān)心結(jié)在圖論中只關(guān)心結(jié)點(diǎn)間是否有連線，而不關(guān)心結(jié)點(diǎn)的位置和連線的形狀。因此，對(duì)于給定的圖而言，點(diǎn)的位置和連線的形狀。因此，對(duì)于給定的圖而言，如果將圖的各結(jié)點(diǎn)安排在不同的位置上，并且用不同如果將圖的各結(jié)點(diǎn)安排在不同的位置上，并且用不同形狀的弧線或直線表示各邊，則可以得到各種不同圖形狀的弧線或直線表示各邊，則可以得到各種不同圖形。所以，同一圖的圖形并不惟一。由于這種圖形表形。所以

18、，同一圖的圖形并不惟一。由于這種圖形表示的任意性，可能出現(xiàn)這樣的情況：看起來(lái)完全不同示的任意性，可能出現(xiàn)這樣的情況：看起來(lái)完全不同的兩種圖形，卻表示著同一個(gè)圖。的兩種圖形，卻表示著同一個(gè)圖。 例如，在圖例如，在圖7.4中，中，(a)和和(b)兩個(gè)圖的圖形不同，兩個(gè)圖的圖形不同，但它們的結(jié)構(gòu)完全相同，是同一個(gè)圖。但它們的結(jié)構(gòu)完全相同，是同一個(gè)圖。 為了描述看起來(lái)不同，而其結(jié)構(gòu)完全相同的圖，為了描述看起來(lái)不同，而其結(jié)構(gòu)完全相同的圖，引入了同構(gòu)的概念。引入了同構(gòu)的概念。 第七章：圖論第七章：圖論第七章：圖論第七章：圖論【定義【定義7.1.10】 設(shè)設(shè)G1= V1,E1 與與G2= V2,E2 是兩是

19、兩個(gè)無(wú)向圖個(gè)無(wú)向圖( (有向圖有向圖) )，若存在雙射函數(shù)，若存在雙射函數(shù)f：V1V2， v1 V1， v2 V1(v1,v2) E1( v1,v2E1)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)(f(v1),f(v2) E2)( f(v1),f(v2)E2)并且并且(v1,v2)( v1,v2 )與與(f(v1),f(v2)( f(v1),f(v2) )的重的重?cái)?shù)相同，則稱(chēng)圖數(shù)相同，則稱(chēng)圖G1與圖與圖G2同構(gòu)。記為同構(gòu)。記為G1G2。雙。雙射函數(shù)射函數(shù)f稱(chēng)為圖稱(chēng)為圖G1與圖與圖G2的同構(gòu)函數(shù)。的同構(gòu)函數(shù)。 第七章：圖論第七章：圖論 兩個(gè)圖同構(gòu)必須滿足下列條件：兩個(gè)圖同構(gòu)必須滿足下列條件： 結(jié)點(diǎn)數(shù)相同。結(jié)點(diǎn)數(shù)相同。 邊

20、數(shù)相同。邊數(shù)相同。 度數(shù)相同的結(jié)點(diǎn)數(shù)相同。度數(shù)相同的結(jié)點(diǎn)數(shù)相同。 這三個(gè)條件是兩個(gè)圖同構(gòu)的必要條件，不是充分條這三個(gè)條件是兩個(gè)圖同構(gòu)的必要條件，不是充分條件。一般的，用上述三個(gè)必要條件判斷兩個(gè)圖是不同構(gòu)件。一般的，用上述三個(gè)必要條件判斷兩個(gè)圖是不同構(gòu)的。的。 兩個(gè)圖同構(gòu)，它們的同構(gòu)函數(shù)必須實(shí)現(xiàn)同度結(jié)點(diǎn)對(duì)兩個(gè)圖同構(gòu)，它們的同構(gòu)函數(shù)必須實(shí)現(xiàn)同度結(jié)點(diǎn)對(duì)應(yīng)同度結(jié)點(diǎn)。應(yīng)同度結(jié)點(diǎn)。 第七章：圖論第七章：圖論 7.1.5補(bǔ)圖、子圖和生成子圖補(bǔ)圖、子圖和生成子圖【定義【定義7.1.11】設(shè)設(shè)G= V,E 是是n階簡(jiǎn)單無(wú)向圖，階簡(jiǎn)單無(wú)向圖，G中的所有結(jié)點(diǎn)和所有能使中的所有結(jié)點(diǎn)和所有能使G成為完全圖的添加邊成為完

21、全圖的添加邊組成的圖稱(chēng)為圖組成的圖稱(chēng)為圖G的相對(duì)于完全圖的補(bǔ)圖，簡(jiǎn)稱(chēng)的相對(duì)于完全圖的補(bǔ)圖，簡(jiǎn)稱(chēng)為為G的補(bǔ)圖。記的補(bǔ)圖。記為為 。若。若G ，則稱(chēng)則稱(chēng)G為自補(bǔ)圖。為自補(bǔ)圖。 在圖在圖7.5中，中，(b)是是(a)的補(bǔ)圖，的補(bǔ)圖，(a)與與(b)同構(gòu)，所同構(gòu)，所以以(a)是自補(bǔ)圖。是自補(bǔ)圖。 GG第七章：圖論第七章：圖論【定義【定義7.1.12】設(shè)設(shè)G= V,E 與與G1= V1,E1 是兩個(gè)圖。是兩個(gè)圖。如果如果V1 V且且E1 E，則稱(chēng)，則稱(chēng)G1是是G的子圖，的子圖，G是是G1的的母圖；如果母圖；如果V1 V且且E1 E，則稱(chēng)，則稱(chēng)G1是是G的真子圖；的真子圖；如果如果V1V且且E1 E則稱(chēng)則

22、稱(chēng)G1是是G的生成子圖。的生成子圖。 在圖在圖7.6中，中，(b)是是(a)的子圖、真的子圖、真子圖、生成子圖、生成子圖。子圖。第七章：圖論第七章：圖論7.2 路和回路路和回路【定義【定義7.2.1】 設(shè)設(shè)G= V,E 是圖，是圖，G中的結(jié)點(diǎn)與邊的交替序列中的結(jié)點(diǎn)與邊的交替序列L：v0e1v1e2v2envn叫做叫做v0到到vn的路。其中的路。其中vi- -1與與vi是是ei的端點(diǎn)，的端點(diǎn)，i=1,n。v0和和vn分別叫做路分別叫做路L的始點(diǎn)和終點(diǎn)。路的始點(diǎn)和終點(diǎn)。路L中邊的條數(shù)叫中邊的條數(shù)叫做該路的長(zhǎng)度。做該路的長(zhǎng)度。 例如，在圖例如，在圖7.7中，中， L1：v5e8v4e5v2e6v5e

23、7v3 是從是從v5到到v3的路，的路，v5是始點(diǎn)，是始點(diǎn)， v3是終點(diǎn)，長(zhǎng)度為是終點(diǎn)，長(zhǎng)度為4。 L2：v1e1v2e3v3 是從是從v1到到v3的路，的路，v1是始點(diǎn)，是始點(diǎn)， v3是終點(diǎn)，長(zhǎng)度為是終點(diǎn)，長(zhǎng)度為2。 在簡(jiǎn)單圖中沒(méi)有平行邊和環(huán)，路在簡(jiǎn)單圖中沒(méi)有平行邊和環(huán)，路L：v0e1v1e2v2envn完全由完全由它的結(jié)點(diǎn)序列它的結(jié)點(diǎn)序列v0v1v2 vn確定。所以，在簡(jiǎn)單圖中的路可以用結(jié)確定。所以，在簡(jiǎn)單圖中的路可以用結(jié)點(diǎn)序列表示。點(diǎn)序列表示。 第七章：圖論第七章：圖論 【定義【定義7.2.2】 設(shè)設(shè)G= V,E 是圖，是圖，L是從是從 v0到到vn的路。若的路。若v0=vn，則稱(chēng)，則稱(chēng)

24、L為回路。若為回路。若L中所有邊各異，則中所有邊各異，則稱(chēng)稱(chēng)L為簡(jiǎn)單路。若此時(shí)又有為簡(jiǎn)單路。若此時(shí)又有v0=vn，則稱(chēng)則稱(chēng)L為簡(jiǎn)單回路。若為簡(jiǎn)單回路。若L中所有結(jié)中所有結(jié)點(diǎn)各異，則稱(chēng)點(diǎn)各異，則稱(chēng)L為基本路。若此時(shí)為基本路。若此時(shí)又有又有v0=vn，則稱(chēng)，則稱(chēng)L為基本回路。若為基本回路。若L既是簡(jiǎn)單路，又是基本路，則稱(chēng)既是簡(jiǎn)單路，又是基本路，則稱(chēng)L為初級(jí)路。若此時(shí)又有為初級(jí)路。若此時(shí)又有v0=vn，則，則稱(chēng)稱(chēng)L為初級(jí)回路。為初級(jí)回路。 在圖在圖7.7中，中，L1是一條簡(jiǎn)單路。是一條簡(jiǎn)單路。L2是一條簡(jiǎn)單路、基本路、初級(jí)路是一條簡(jiǎn)單路、基本路、初級(jí)路。 第七章：圖論第七章：圖論【 定理定理7.2.

25、1】 在在n階圖階圖G中，若從結(jié)點(diǎn)中，若從結(jié)點(diǎn)vi到到vj(vivj)存在一條存在一條路，則必存在長(zhǎng)度小于等于路，則必存在長(zhǎng)度小于等于n- -1的路。的路。 證明：證明：設(shè)設(shè)L：vie1v1e2v2ejvj是是G中一條從結(jié)點(diǎn)中一條從結(jié)點(diǎn)vi到到vj長(zhǎng)度長(zhǎng)度為為l的路，路上有的路，路上有l(wèi)+1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 若若ln- -1，則定理已證。，則定理已證。 否則，否則，ln- -1，此時(shí)，此時(shí)，l+1n，即路，即路L上的結(jié)點(diǎn)數(shù)上的結(jié)點(diǎn)數(shù)l+1大大于圖于圖G中的結(jié)點(diǎn)數(shù)中的結(jié)點(diǎn)數(shù)n，此路上必有相同結(jié)點(diǎn)。設(shè)，此路上必有相同結(jié)點(diǎn)。設(shè)vk和和vs相同。相同。于是，此路兩次通過(guò)同一個(gè)結(jié)點(diǎn)于是，此路兩次通過(guò)同一

26、個(gè)結(jié)點(diǎn)vk(vs)，所以在，所以在L上存在上存在vs到自到自身的回路身的回路Cks。在。在L上刪除上刪除Cks上的一切邊和除上的一切邊和除vs以外的一切結(jié)以外的一切結(jié)點(diǎn)，得路點(diǎn)，得路L1：vie1v1ekvsejvj。L1仍為從結(jié)點(diǎn)仍為從結(jié)點(diǎn)vi到到vj的路，且的路，且長(zhǎng)度至少比長(zhǎng)度至少比L減少減少1。若路。若路L1的長(zhǎng)度小于等于的長(zhǎng)度小于等于n- -1，則定理已，則定理已證。否則，重復(fù)上述過(guò)程。由于證。否則，重復(fù)上述過(guò)程。由于G有有n個(gè)結(jié)點(diǎn)，經(jīng)過(guò)有限步后，個(gè)結(jié)點(diǎn)，經(jīng)過(guò)有限步后，必得到從必得到從vi到到vj長(zhǎng)度小于等于長(zhǎng)度小于等于n- -1的路。的路。第七章：圖論第七章：圖論推論推論 在在n階

27、圖階圖G中，若從結(jié)點(diǎn)中，若從結(jié)點(diǎn)vi到到vj(vivj)存在路，存在路，則必存在長(zhǎng)度小于等于則必存在長(zhǎng)度小于等于n- -1的初級(jí)路。的初級(jí)路。 由定理由定理7.2.1的證明過(guò)程知，本推論成立。的證明過(guò)程知，本推論成立。 類(lèi)似的可證明下列定理和推論。類(lèi)似的可證明下列定理和推論?！径ɡ怼径ɡ?.2.2】 在在n階圖階圖G中，若存在結(jié)點(diǎn)中，若存在結(jié)點(diǎn)vi到自身到自身的回路，則必存在的回路，則必存在vi到自身長(zhǎng)度小于等于到自身長(zhǎng)度小于等于n的回路。的回路。 推論推論 在在n階圖階圖G中，若存在結(jié)點(diǎn)中，若存在結(jié)點(diǎn)vi到自身的簡(jiǎn)單回到自身的簡(jiǎn)單回路，則必存在路，則必存在vi到自身長(zhǎng)度小于等于到自身長(zhǎng)度小于

28、等于n的初級(jí)回路。的初級(jí)回路。 【定義【定義7.2.3】 在無(wú)向圖在無(wú)向圖G中，如果結(jié)點(diǎn)中，如果結(jié)點(diǎn)u和結(jié)點(diǎn)和結(jié)點(diǎn)v之間存在之間存在一條路，則稱(chēng)結(jié)點(diǎn)一條路，則稱(chēng)結(jié)點(diǎn)u和結(jié)點(diǎn)和結(jié)點(diǎn)v連通。記為連通。記為uv。規(guī)定，。規(guī)定，G中中任意結(jié)點(diǎn)任意結(jié)點(diǎn)v和自身連通，即和自身連通，即vv。 在無(wú)向圖中，如果結(jié)點(diǎn)在無(wú)向圖中，如果結(jié)點(diǎn)u和結(jié)點(diǎn)和結(jié)點(diǎn)v連通，即連通，即uv，那么，那么，結(jié)點(diǎn)結(jié)點(diǎn)v和結(jié)點(diǎn)和結(jié)點(diǎn)u連通，即連通，即vu。所以，無(wú)向圖結(jié)點(diǎn)間的連通。所以，無(wú)向圖結(jié)點(diǎn)間的連通是對(duì)稱(chēng)的。是對(duì)稱(chēng)的。 設(shè)設(shè)G= V,E 是無(wú)向圖，在圖是無(wú)向圖，在圖G的結(jié)點(diǎn)集的結(jié)點(diǎn)集V上建立一個(gè)上建立一個(gè)二元關(guān)系二元關(guān)系R：R=u

29、,v | u Vv Vu和和v連通連通 R叫做無(wú)向圖叫做無(wú)向圖G的結(jié)點(diǎn)集的結(jié)點(diǎn)集V上的連通關(guān)系。上的連通關(guān)系。 因?yàn)橐驗(yàn)镽是自反的、對(duì)稱(chēng)的、傳遞的，所以是自反的、對(duì)稱(chēng)的、傳遞的，所以R是是V上的等上的等價(jià)關(guān)系。無(wú)向圖價(jià)關(guān)系。無(wú)向圖G的結(jié)點(diǎn)集的結(jié)點(diǎn)集V上的連通關(guān)系是等價(jià)關(guān)系。上的連通關(guān)系是等價(jià)關(guān)系。第七章：圖論第七章：圖論 設(shè)設(shè)G是圖是圖7.8。結(jié)點(diǎn)集。結(jié)點(diǎn)集V上的連通關(guān)系為上的連通關(guān)系為R，以下驗(yàn)證，以下驗(yàn)證R是是V上的等價(jià)關(guān)系，并找出所有等價(jià)類(lèi)。上的等價(jià)關(guān)系，并找出所有等價(jià)類(lèi)。 R=a,a , a,b , a,c , b,a , b,b , b,c , c,a , c,b , c,c , d

30、,d , e,e , e,f , e,g , e,h , f,e , f,f , f,g , f,h , g,e , g,f , g,g , g,h , h,e , h,f , h,g , h,h = a,b,c a,b,c d d e,f,g,h e,f,g,h 根據(jù)定義，根據(jù)定義，R是是V上的等價(jià)關(guān)上的等價(jià)關(guān)系。等價(jià)類(lèi)有三系。等價(jià)類(lèi)有三個(gè)，分別是：個(gè)，分別是： a,b,c ， d ， e,f,g,h 。第七章：圖論第七章：圖論【定義【定義7.2.4】 若無(wú)向圖若無(wú)向圖G中的任何兩個(gè)結(jié)點(diǎn)都是連通中的任何兩個(gè)結(jié)點(diǎn)都是連通的，則稱(chēng)的，則稱(chēng)G為連通圖。規(guī)定，平凡圖是連通圖。為連通圖。規(guī)定，平凡圖是

31、連通圖?！径x【定義7.2.5】 設(shè)設(shè)G= V,E 是圖是圖 V1 V且且V1，E1是是G中兩個(gè)端點(diǎn)都在中兩個(gè)端點(diǎn)都在V1中的邊中的邊組成的集合，圖組成的集合，圖G1= V1,E1 叫做叫做G的由的由V1導(dǎo)出的子圖，導(dǎo)出的子圖，記為記為GV1。 E2 E且且E2，V2是由是由E2中的邊所關(guān)聯(lián)的結(jié)點(diǎn)中的邊所關(guān)聯(lián)的結(jié)點(diǎn)組成的集合，圖組成的集合，圖G2= V2,E2 叫做叫做G的由的由E2導(dǎo)出的子圖，導(dǎo)出的子圖，記為記為GE2。 在圖在圖7.9中，設(shè)圖中，設(shè)圖G為為(a)，取，取V1= a,b,c ，則，則G的由的由V1導(dǎo)出的子圖導(dǎo)出的子圖GV1是是(b)。取。取E2= (a,b),(d,c) ，G

32、的由的由E2導(dǎo)出的子圖導(dǎo)出的子圖GE2是是(c)。第七章：圖論第七章：圖論第七章：圖論第七章：圖論【定義【定義7.2.6】 設(shè)設(shè)G= V,E 是無(wú)向圖，是無(wú)向圖， R是是V上的連通上的連通關(guān)系，關(guān)系，V/R= Vi Vi是是R的等價(jià)類(lèi)，的等價(jià)類(lèi)，i=1,k 是是V關(guān)于關(guān)于R的商集，的商集，GVi是是Vi導(dǎo)出的子圖，稱(chēng)導(dǎo)出的子圖，稱(chēng)GVi( i=1, k)為為G的連通分支。的連通分支。G的連通分支數(shù)記為的連通分支數(shù)記為W(G)。 設(shè)圖設(shè)圖7.8為為G，在，在G中，連通關(guān)系中，連通關(guān)系R的三個(gè)等價(jià)類(lèi)的三個(gè)等價(jià)類(lèi)是是 a,b,c ， d ， e,f,g,h ，它們導(dǎo)出的，它們導(dǎo)出的G的子圖分別的子圖

33、分別是圖是圖7.8中的中的(a)，(b)，(c)。它們都是。它們都是G的連通分支。的連通分支。G的連通分支數(shù)的連通分支數(shù)W(G)=3。 每一個(gè)連通分支中任何兩個(gè)結(jié)點(diǎn)是連通的，而位每一個(gè)連通分支中任何兩個(gè)結(jié)點(diǎn)是連通的，而位于不同連通分支中的任何兩個(gè)結(jié)點(diǎn)是不連通的。即每于不同連通分支中的任何兩個(gè)結(jié)點(diǎn)是不連通的。即每一個(gè)連通分支都是原圖的最大的連通子圖。在圖一個(gè)連通分支都是原圖的最大的連通子圖。在圖7.8中，中，(a)，(b)，(c)都是最大的連通子圖。都是最大的連通子圖。 第七章：圖論第七章：圖論【定義【定義7.2.7】 設(shè)設(shè)u，v是無(wú)向圖是無(wú)向圖G中的任意兩個(gè)結(jié)點(diǎn)，若中的任意兩個(gè)結(jié)點(diǎn)，若u和和v

34、連連通，則通，則u和和v之間最短路的長(zhǎng)叫做結(jié)點(diǎn)之間最短路的長(zhǎng)叫做結(jié)點(diǎn)u與結(jié)點(diǎn)與結(jié)點(diǎn)v的距離，記為的距離，記為d(u,v)。若。若u和和v不連通，規(guī)定，不連通，規(guī)定，u與與v的距離為的距離為。即。即d(u,v)= 設(shè)設(shè)G= V,E 是無(wú)向圖，是無(wú)向圖，u、v和和w是是V中的任意結(jié)點(diǎn)，中的任意結(jié)點(diǎn)，G的結(jié)的結(jié)點(diǎn)間的距離有以下的性質(zhì)：點(diǎn)間的距離有以下的性質(zhì)： d(u,v)0 d(u,u)=0 d(u,v)d(v,w)d(u,w) d(u,v)=d(v,u) 在在n階無(wú)向完全圖階無(wú)向完全圖Kn中，每?jī)蓚€(gè)不同結(jié)點(diǎn)間都有一條邊，中，每?jī)蓚€(gè)不同結(jié)點(diǎn)間都有一條邊，它們的距離是它們的距離是1。在零圖中，每?jī)蓚€(gè)不

35、同結(jié)點(diǎn)間都沒(méi)有路，它。在零圖中，每?jī)蓚€(gè)不同結(jié)點(diǎn)間都沒(méi)有路，它們的距離都是們的距離都是。 在圖在圖G中刪除一個(gè)結(jié)點(diǎn)，就是將這個(gè)結(jié)點(diǎn)與它的所有關(guān)聯(lián)中刪除一個(gè)結(jié)點(diǎn)，就是將這個(gè)結(jié)點(diǎn)與它的所有關(guān)聯(lián)邊全部刪除。刪除一個(gè)邊，則僅去掉這個(gè)邊。邊全部刪除。刪除一個(gè)邊，則僅去掉這個(gè)邊。 第七章：圖論第七章：圖論【定義【定義7.2.8】設(shè)設(shè)G= V,E 是無(wú)向連通圖，是無(wú)向連通圖，V1 V且且V1，滿，滿足：足： 刪除刪除V1的所有結(jié)點(diǎn)，得到的子圖是不連通的。的所有結(jié)點(diǎn)，得到的子圖是不連通的。 刪除刪除V1的任何真子集，得到的子圖是連通的。的任何真子集，得到的子圖是連通的。則稱(chēng)則稱(chēng)V1是是G的點(diǎn)割集。如果某一個(gè)結(jié)點(diǎn)

36、組成了點(diǎn)割集，則稱(chēng)的點(diǎn)割集。如果某一個(gè)結(jié)點(diǎn)組成了點(diǎn)割集，則稱(chēng)該點(diǎn)為割點(diǎn)。該點(diǎn)為割點(diǎn)。 在圖在圖7.10中，中， b,d ， c ， e 都是都是點(diǎn)割集，結(jié)點(diǎn)點(diǎn)割集，結(jié)點(diǎn)c和結(jié)點(diǎn)和結(jié)點(diǎn)e都是割點(diǎn)。雖然刪除都是割點(diǎn)。雖然刪除結(jié)點(diǎn)結(jié)點(diǎn)a和和c圖成為不連圖成為不連通的，但因通的，但因 c 是是 a,c 的真子集，所以的真子集，所以 a,c 不是點(diǎn)割集。不是點(diǎn)割集。第七章：圖論第七章：圖論【定義【定義7.2.9】設(shè)設(shè)G= V,E 是無(wú)向連通圖，如果是無(wú)向連通圖，如果G不是完全圖，不是完全圖，k(G)=min |V1| V1是是G的點(diǎn)割集的點(diǎn)割集 稱(chēng)稱(chēng)為圖為圖G的點(diǎn)連通度。如果的點(diǎn)連通度。如果G是完全圖，

37、規(guī)定是完全圖，規(guī)定n階無(wú)階無(wú)向完全圖向完全圖Kn的點(diǎn)連通度為的點(diǎn)連通度為n1，即，即k(Kn)=n1。規(guī)定不連通圖規(guī)定不連通圖G的點(diǎn)連通度為的點(diǎn)連通度為0。即。即k(G)= 0。 圖圖7.10是無(wú)向連通圖，但不是完全圖，存在是無(wú)向連通圖，但不是完全圖，存在割點(diǎn)割點(diǎn)c和和e，所以點(diǎn)連通度是，所以點(diǎn)連通度是1。 無(wú)向連通圖的點(diǎn)連通度的物理意義是：要使無(wú)向連通圖的點(diǎn)連通度的物理意義是：要使G成為不連通的最少要?jiǎng)h除的結(jié)點(diǎn)數(shù)。圖成為不連通的最少要?jiǎng)h除的結(jié)點(diǎn)數(shù)。圖7.10的的點(diǎn)連通度是點(diǎn)連通度是1，最少刪除一個(gè)結(jié)點(diǎn)，圖成為不連，最少刪除一個(gè)結(jié)點(diǎn)，圖成為不連通的，例如刪除結(jié)點(diǎn)通的，例如刪除結(jié)點(diǎn)c或結(jié)點(diǎn)或結(jié)點(diǎn)

38、e。 第七章：圖論第七章：圖論【定義【定義7.2.10】設(shè)設(shè)G= V,E 是無(wú)向連通圖，是無(wú)向連通圖，E1 E且且E1，滿足：，滿足： 刪除刪除E1的所有邊，得到的子圖是不連通的。的所有邊，得到的子圖是不連通的。 刪除刪除E1的任何真子集，得到的子圖是連通的的任何真子集，得到的子圖是連通的則稱(chēng)則稱(chēng)E1是是G的邊割集。如果某一條邊組成了邊割集，的邊割集。如果某一條邊組成了邊割集，則稱(chēng)該邊為割邊或橋。則稱(chēng)該邊為割邊或橋。 在圖在圖7.10中，集合中，集合 (c,e) 、 (e,f) 、 (a,b),(d,c) 和和 (a,d),(b,c) 都是都是G的邊割集，無(wú)向邊的邊割集，無(wú)向邊(c,e)和和(

39、e,f)為割邊。雖然刪除邊為割邊。雖然刪除邊(a,d)、(a,b)和和(d,c)圖成為不連通的，但因集合圖成為不連通的，但因集合 (a,b),(d,c) 是集合是集合 (a,d),(a,b),(d,c) 的真子集，所以的真子集，所以 (a,d),(a,b),(d,c) 不是邊割集。不是邊割集。第七章：圖論第七章：圖論【定義【定義7.2.11】設(shè)設(shè)G= V,E 是無(wú)向連通圖，如果是無(wú)向連通圖，如果G是是非平凡圖，非平凡圖， (G)=min |E1| E1是是G的邊割集的邊割集 稱(chēng)為稱(chēng)為G的的邊連通度。如果邊連通度。如果G是平凡圖，規(guī)定是平凡圖，規(guī)定G的邊連通度為的邊連通度為0。規(guī)定不連通圖規(guī)定不

40、連通圖G的邊連通度為的邊連通度為0，即，即 (G)=0。 圖圖7.10是無(wú)向連通圖，但不是平凡圖，存在割邊是無(wú)向連通圖，但不是平凡圖，存在割邊(c,e)和和(e,f)，所以，它的邊連通度是，所以，它的邊連通度是1。 無(wú)向連通圖的邊連通度的物理意義是：要使無(wú)向連通圖的邊連通度的物理意義是：要使G成成為不連通的最少要?jiǎng)h除的邊數(shù)。圖為不連通的最少要?jiǎng)h除的邊數(shù)。圖7.10的邊連通度是的邊連通度是1，最少刪除一條邊，最少刪除一條邊，圖就會(huì)圖就會(huì)成為不連通的，例如刪成為不連通的，例如刪除除割邊割邊(c,e)或或(e,f)。 無(wú)向圖無(wú)向圖G的點(diǎn)連通度的點(diǎn)連通度k(G)、邊連通度、邊連通度 (G)和最小和最小

41、度度 (G)有下列的關(guān)系：有下列的關(guān)系： 第七章：圖論第七章：圖論【定理【定理7.2.3】設(shè)設(shè)G= V,E 為任意無(wú)向圖，則為任意無(wú)向圖，則k(G) (G) (G) 證明：證明：如果如果G是不連通的，由點(diǎn)連通度和邊連通是不連通的，由點(diǎn)連通度和邊連通度的定義有度的定義有k(G)= (G)=0，所以，所以 k(G) (G) (G) 如果如果G是連通圖。是連通圖。 先證明先證明 (G) (G) 如果如果G是平凡圖，是平凡圖， (G)=0 (G)，即，即 (G) (G) 如果如果G是非平凡圖，設(shè)是非平凡圖，設(shè)n= (G)=min deg(v)|v V ，則存在則存在G的一個(gè)結(jié)點(diǎn)的一個(gè)結(jié)點(diǎn)v，它關(guān)聯(lián)了，

42、它關(guān)聯(lián)了n條邊，而其它結(jié)點(diǎn)關(guān)條邊，而其它結(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)大于等于聯(lián)的邊數(shù)大于等于n，將，將v關(guān)聯(lián)的這關(guān)聯(lián)的這n條邊刪除，條邊刪除，G成為成為不連通的。從而這不連通的。從而這n條邊或這條邊或這n條邊中的幾條邊組成一條邊中的幾條邊組成一個(gè)邊割集，即存在一個(gè)邊割集的基數(shù)小于等于個(gè)邊割集，即存在一個(gè)邊割集的基數(shù)小于等于n，所以，所以第七章：圖論第七章：圖論 min |E 1| | E 1是是G的邊割集的邊割集 n=min deg(v) | v V ，即即 (G) (G) 再證再證k(G) (G) 設(shè)設(shè) (G)=1，G有一條割邊，此邊的任一端點(diǎn)是割點(diǎn)，有一條割邊，此邊的任一端點(diǎn)是割點(diǎn)，k(G)=1。所以。

43、所以k(G) (G)成立。成立。 設(shè)設(shè) (G)2，則可刪除某，則可刪除某 (G)條邊，使條邊，使G成為不連通的，成為不連通的，而刪除其中的而刪除其中的 (G)1條邊，它仍然是連通的且有一個(gè)橋，條邊，它仍然是連通的且有一個(gè)橋，設(shè)該橋?yàn)樵O(shè)該橋?yàn)閑=(u,v)。對(duì)這。對(duì)這 (G)1條邊選取一個(gè)不同于條邊選取一個(gè)不同于u，也也不同于不同于v的端點(diǎn)，把這些端點(diǎn)刪除，則必至少刪除了這的端點(diǎn)，把這些端點(diǎn)刪除，則必至少刪除了這 ( G ) 1 條 邊 。 若 這 樣 產(chǎn) 生 的 圖 是 不 連 通 的 ， 則條 邊 。 若 這 樣 產(chǎn) 生 的 圖 是 不 連 通 的 ， 則k(G) (G)1 (G)。若這樣產(chǎn)

44、生的圖是連通的，則。若這樣產(chǎn)生的圖是連通的，則e=(u,v)仍是橋。此時(shí)再刪除仍是橋。此時(shí)再刪除u或或v，就必產(chǎn)生了一個(gè)不連通圖，就必產(chǎn)生了一個(gè)不連通圖，故故k(G) (G) 由由和和得得k(G) (G) (G) 第七章：圖論第七章：圖論 圖圖7.11是無(wú)向連通圖，點(diǎn)連通度是無(wú)向連通圖，點(diǎn)連通度k(G)=1，邊連通度，邊連通度 (G)=2，最小度，最小度 (G)=3，此圖滿足，此圖滿足k(G) (G) (G)。第七章：圖論第七章：圖論【定理【定理7.2.4】在無(wú)向連通圖在無(wú)向連通圖G中，結(jié)點(diǎn)中，結(jié)點(diǎn)v是割點(diǎn)的充分必要條是割點(diǎn)的充分必要條件是存在兩個(gè)結(jié)點(diǎn)件是存在兩個(gè)結(jié)點(diǎn)u和和w，使結(jié)點(diǎn)，使結(jié)點(diǎn)u

45、和和w之間的每一條路都通過(guò)之間的每一條路都通過(guò)v。 證明：證明：設(shè)設(shè)v是割點(diǎn)，證明存在兩個(gè)結(jié)點(diǎn)是割點(diǎn)，證明存在兩個(gè)結(jié)點(diǎn)u和和w，使結(jié)點(diǎn)，使結(jié)點(diǎn)u和和w之間的每一條路都通過(guò)之間的每一條路都通過(guò)v。 v是割點(diǎn)，刪除是割點(diǎn)，刪除v得得G，G至少包含兩個(gè)連通分支，設(shè)其至少包含兩個(gè)連通分支，設(shè)其中的兩個(gè)為中的兩個(gè)為G1= V1,E1 和和G2= V2,E2 ， u V1， w V2，因?yàn)?，因?yàn)镚連通，在連通，在G中中u和和w之間必有路，設(shè)之間必有路，設(shè)L是它們之間任意一條路。是它們之間任意一條路。在在G中，由于中，由于u和和w屬于兩個(gè)不同連通分支，所以，屬于兩個(gè)不同連通分支，所以，u和和w之間之間必沒(méi)有

46、路。故必沒(méi)有路。故L必通過(guò)必通過(guò)v。 設(shè)存在兩個(gè)結(jié)點(diǎn)設(shè)存在兩個(gè)結(jié)點(diǎn)u和和w，使結(jié)點(diǎn)，使結(jié)點(diǎn)u和和w之間的每一條路都通之間的每一條路都通過(guò)過(guò)v，證明，證明v是割點(diǎn)。是割點(diǎn)。 刪除刪除v得子圖得子圖G，因?yàn)榻Y(jié)點(diǎn)，因?yàn)榻Y(jié)點(diǎn)u和和w之間的每一條路都通過(guò)之間的每一條路都通過(guò)v，所以在所以在G中結(jié)點(diǎn)中結(jié)點(diǎn)u和和w之間必?zé)o路，即結(jié)點(diǎn)之間必?zé)o路，即結(jié)點(diǎn)u和和w不連通。由連不連通。由連通圖的定義知，通圖的定義知，G是不連通的，故是不連通的，故v是是G的割點(diǎn)。的割點(diǎn)。 第七章：圖論第七章：圖論【定義【定義7.2.12】在有向圖在有向圖G中，結(jié)點(diǎn)中，結(jié)點(diǎn)u到結(jié)點(diǎn)到結(jié)點(diǎn)v存在一條路，存在一條路，則稱(chēng)結(jié)點(diǎn)則稱(chēng)結(jié)點(diǎn)u到結(jié)

47、點(diǎn)到結(jié)點(diǎn)v可達(dá)。記為可達(dá)。記為uv。如果。如果u到到v可達(dá)且可達(dá)且v到到u也可達(dá)，稱(chēng)結(jié)點(diǎn)也可達(dá)，稱(chēng)結(jié)點(diǎn)u和結(jié)點(diǎn)和結(jié)點(diǎn)v相互可達(dá)。記為相互可達(dá)。記為uv。 規(guī)規(guī)定，定，G中任何結(jié)點(diǎn)中任何結(jié)點(diǎn)v自己到自己可達(dá)，即自己到自己可達(dá)，即vv。【定義【定義7.2.13】在有向圖在有向圖G= V,E 中，中，u V，v V，若結(jié)，若結(jié)點(diǎn)點(diǎn)u到結(jié)點(diǎn)到結(jié)點(diǎn)v可達(dá)，可達(dá)，u到到v最短路的長(zhǎng)稱(chēng)為結(jié)點(diǎn)最短路的長(zhǎng)稱(chēng)為結(jié)點(diǎn)u到結(jié)點(diǎn)到結(jié)點(diǎn)v的的距離。記為距離。記為d u,v 。若。若u到到v不可達(dá)，規(guī)定，不可達(dá)，規(guī)定，u到到v的距離的距離為為。即。即d u,v =。 對(duì)于有向圖對(duì)于有向圖G中的任意結(jié)點(diǎn)中的任意結(jié)點(diǎn)u,v和和

48、w，結(jié)點(diǎn)間的距離，結(jié)點(diǎn)間的距離有以下的性質(zhì)：有以下的性質(zhì)： d u,v 0 d u,u =0 d u,v d v,w d u,w 第七章：圖論第七章：圖論【定義【定義7.2.14】在簡(jiǎn)單有向圖在簡(jiǎn)單有向圖G中，對(duì)于任意兩個(gè)結(jié)中，對(duì)于任意兩個(gè)結(jié)點(diǎn)點(diǎn)u和和v， 如果結(jié)點(diǎn)如果結(jié)點(diǎn)u到結(jié)點(diǎn)到結(jié)點(diǎn)v可達(dá)或結(jié)點(diǎn)可達(dá)或結(jié)點(diǎn)v到結(jié)點(diǎn)到結(jié)點(diǎn)u可達(dá)，可達(dá)，則稱(chēng)則稱(chēng)G為單向?yàn)閱蜗?側(cè)側(cè))連通的。連通的。 如果結(jié)點(diǎn)如果結(jié)點(diǎn)u和結(jié)點(diǎn)和結(jié)點(diǎn)v互相可達(dá)，則稱(chēng)互相可達(dá)，則稱(chēng)G為強(qiáng)連為強(qiáng)連通的。通的。 如果略去方向得到的無(wú)向圖是連通的，則稱(chēng)如果略去方向得到的無(wú)向圖是連通的，則稱(chēng)G為弱連通的。為弱連通的。 在圖在圖7.12中，中

49、，(a)是強(qiáng)連通的、單向是強(qiáng)連通的、單向(側(cè)側(cè))連通的連通的和弱連通的。和弱連通的。(b)是單向是單向(側(cè)側(cè))連通的和弱連通的，但連通的和弱連通的，但不是強(qiáng)連通的。不是強(qiáng)連通的。(c)是弱連通的，但不是單向是弱連通的，但不是單向(側(cè)側(cè))連連通的，也不是強(qiáng)連通的。通的，也不是強(qiáng)連通的。第七章：圖論第七章：圖論 一般地說(shuō)，若有向圖一般地說(shuō)，若有向圖G是強(qiáng)連通的，則必是單是強(qiáng)連通的，則必是單向向(側(cè)側(cè))連通的和弱連通的；若有向圖連通的和弱連通的；若有向圖G是單向是單向(側(cè)側(cè))連連通的，則必是弱連通的。反之不真。通的，則必是弱連通的。反之不真。第七章：圖論第七章：圖論【定理定理7.2.5】一個(gè)有向圖一

50、個(gè)有向圖G是強(qiáng)連通的充分必要條件是強(qiáng)連通的充分必要條件是是G中有一個(gè)回路至少包含中有一個(gè)回路至少包含G的每個(gè)結(jié)點(diǎn)一次。的每個(gè)結(jié)點(diǎn)一次。 證明：證明：設(shè)設(shè)G中有一個(gè)回路至少包含中有一個(gè)回路至少包含G的每個(gè)結(jié)點(diǎn)的每個(gè)結(jié)點(diǎn)一次，下證一次，下證G是強(qiáng)連通的。是強(qiáng)連通的。 G中有一個(gè)回路至少包含每個(gè)結(jié)點(diǎn)一次，則中有一個(gè)回路至少包含每個(gè)結(jié)點(diǎn)一次，則G中中的任意兩個(gè)結(jié)點(diǎn)通過(guò)回路互相可達(dá)。所以的任意兩個(gè)結(jié)點(diǎn)通過(guò)回路互相可達(dá)。所以G是強(qiáng)連通是強(qiáng)連通的。的。 設(shè)設(shè)G是強(qiáng)連通的，下證是強(qiáng)連通的，下證G中有一個(gè)回路至少包含中有一個(gè)回路至少包含G的每個(gè)結(jié)點(diǎn)一次。的每個(gè)結(jié)點(diǎn)一次。 若不然，存在結(jié)點(diǎn)若不然，存在結(jié)點(diǎn)v不在不

51、在G的回路上，且的回路上，且v不與其不與其它所有結(jié)點(diǎn)不能互相可達(dá)，這與它所有結(jié)點(diǎn)不能互相可達(dá)，這與G是強(qiáng)連通的矛盾。是強(qiáng)連通的矛盾。故故G中有一個(gè)回路至少包含中有一個(gè)回路至少包含G的每個(gè)結(jié)點(diǎn)一次。的每個(gè)結(jié)點(diǎn)一次。第七章：圖論第七章：圖論【定理【定理7.2.6】一個(gè)有向圖一個(gè)有向圖G是單向連通的充分必是單向連通的充分必要條件是要條件是G中有一個(gè)路至少包含每個(gè)結(jié)點(diǎn)一次。中有一個(gè)路至少包含每個(gè)結(jié)點(diǎn)一次。 證明略證明略?！径x【定義7.2.15】在簡(jiǎn)單有向圖在簡(jiǎn)單有向圖G中，具有強(qiáng)中，具有強(qiáng)(單向，單向，弱弱)連通性質(zhì)的最大子圖叫做強(qiáng)連通性質(zhì)的最大子圖叫做強(qiáng)(單向，弱單向，弱)分圖。分圖。 在圖在圖7

52、.13(a)中中，由由 v1,v2,v3,v4 導(dǎo)出的子圖是導(dǎo)出的子圖是強(qiáng) 分 圖 ，強(qiáng) 分 圖 ， v5 導(dǎo) 出 的 子 圖 也 是 強(qiáng) 分 圖 。 由導(dǎo) 出 的 子 圖 也 是 強(qiáng) 分 圖 。 由 v1,v2,v3,v4,v5 導(dǎo)出的子圖是單向分圖，也是弱分導(dǎo)出的子圖是單向分圖，也是弱分圖。圖。 在圖在圖7.13 (b) 中，中， v1 ， v2 ， v3 ， v4 導(dǎo)出導(dǎo)出的子圖是強(qiáng)分圖，的子圖是強(qiáng)分圖， v1,v2,v3 ，和，和 v1,v3,v4 導(dǎo)出的子導(dǎo)出的子圖是單向分圖，圖是單向分圖， v1,v2,v3,v4 導(dǎo)出了弱分圖。導(dǎo)出了弱分圖。 第七章：圖論第七章：圖論第七章：圖論第

53、七章：圖論【定理【定理7.2.7】在有向圖在有向圖G= V,E 中，每一個(gè)結(jié)點(diǎn)位中，每一個(gè)結(jié)點(diǎn)位于且只位于一個(gè)強(qiáng)分圖中。于且只位于一個(gè)強(qiáng)分圖中。 證明：證明： v V，令，令V1是是G中所有與中所有與v互相可達(dá)互相可達(dá)的結(jié)點(diǎn)組成的集合，當(dāng)然的結(jié)點(diǎn)組成的集合，當(dāng)然v V1， V1導(dǎo)出的子圖是導(dǎo)出的子圖是G的強(qiáng)分圖。故的強(qiáng)分圖。故G的每一個(gè)結(jié)點(diǎn)位于一個(gè)強(qiáng)分圖中。的每一個(gè)結(jié)點(diǎn)位于一個(gè)強(qiáng)分圖中。 設(shè)設(shè)G1= V1,E1 和和G2= V2,E2 是是G的兩個(gè)強(qiáng)分的兩個(gè)強(qiáng)分圖，設(shè)圖，設(shè)v V1且且v V2，則，則v與與G1中的所有結(jié)點(diǎn)相互可中的所有結(jié)點(diǎn)相互可達(dá)且與達(dá)且與G2中的所有結(jié)點(diǎn)相互可達(dá)。于是中的所

54、有結(jié)點(diǎn)相互可達(dá)。于是G1中的結(jié)點(diǎn)中的結(jié)點(diǎn)與與G2中的結(jié)點(diǎn)通過(guò)中的結(jié)點(diǎn)通過(guò)v相互可達(dá)。這與相互可達(dá)。這與G1和和G2是強(qiáng)分是強(qiáng)分圖相矛盾。故圖相矛盾。故G的每一個(gè)結(jié)點(diǎn)只位于一個(gè)強(qiáng)分圖中。的每一個(gè)結(jié)點(diǎn)只位于一個(gè)強(qiáng)分圖中。 第七章：圖論第七章：圖論7.3圖的矩陣表示圖的矩陣表示【定義【定義7.3.1】設(shè)設(shè) G= V,E 是一個(gè)簡(jiǎn)單圖，是一個(gè)簡(jiǎn)單圖，V= v1,v2,vn A(G)=(aij) nn 其中：其中： i ,j=1,n稱(chēng)稱(chēng)A(G)為為G的鄰接矩陣。簡(jiǎn)記為的鄰接矩陣。簡(jiǎn)記為A。 01jivvvvajijiij無(wú)邊或到有邊到第七章：圖論第七章：圖論0111101011011010)(GA 例如

55、圖例如圖7.14的鄰接矩陣為的鄰接矩陣為： 第七章：圖論第七章：圖論又如圖又如圖7.15(a)的鄰接矩陣為：的鄰接矩陣為： 0001101111000010)(GA第七章：圖論第七章：圖論 鄰接矩陣具有以下性質(zhì)：鄰接矩陣具有以下性質(zhì)： 鄰接矩陣的元素全是鄰接矩陣的元素全是0或或1。這樣的矩陣叫布爾矩陣。這樣的矩陣叫布爾矩陣。鄰接矩陣是布爾矩陣。鄰接矩陣是布爾矩陣。 無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)陣，有向圖的鄰接矩陣不無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)陣，有向圖的鄰接矩陣不一定是對(duì)稱(chēng)陣。一定是對(duì)稱(chēng)陣。 鄰接矩陣與結(jié)點(diǎn)在圖中標(biāo)定次序有關(guān)。例如圖鄰接矩陣與結(jié)點(diǎn)在圖中標(biāo)定次序有關(guān)。例如圖7.15(a)的鄰接矩陣是的鄰接矩

56、陣是A(G)，若將圖，若將圖7.15(a)中的接點(diǎn)中的接點(diǎn)v1和和v2的標(biāo)定次序調(diào)換，得到圖的標(biāo)定次序調(diào)換，得到圖7.15(b)，圖，圖9.23(b)的鄰接矩陣是的鄰接矩陣是A(G)。0010101100011100)(GA第七章：圖論第七章：圖論 考察考察A(G)和和A(G)發(fā)現(xiàn)，先將發(fā)現(xiàn)，先將A(G)的第一行與第二行對(duì)調(diào)，的第一行與第二行對(duì)調(diào)，再將第一列與第二列對(duì)調(diào)可得到再將第一列與第二列對(duì)調(diào)可得到A(G)。稱(chēng)。稱(chēng)A(G)與與A(G)是置換是置換等價(jià)的。等價(jià)的。 一般地說(shuō)，把一般地說(shuō)，把n階方陣階方陣A的某些行對(duì)調(diào)，再把相應(yīng)的列做的某些行對(duì)調(diào)，再把相應(yīng)的列做同樣的對(duì)調(diào)，得到一個(gè)新的同樣的對(duì)

57、調(diào)，得到一個(gè)新的n階方陣階方陣A，則稱(chēng)，則稱(chēng)A與與A是置換等是置換等價(jià)的?？梢宰C明置換等價(jià)是價(jià)的?？梢宰C明置換等價(jià)是n階布爾方陣集合上的等價(jià)關(guān)系。階布爾方陣集合上的等價(jià)關(guān)系。 雖然，對(duì)于同一個(gè)圖，由于結(jié)點(diǎn)的標(biāo)定次序不同，而得雖然，對(duì)于同一個(gè)圖，由于結(jié)點(diǎn)的標(biāo)定次序不同，而得到不同的鄰接矩陣，但是這些鄰接矩陣是置換等價(jià)的。今后到不同的鄰接矩陣，但是這些鄰接矩陣是置換等價(jià)的。今后略去結(jié)點(diǎn)標(biāo)定次序的任意性，取任意一個(gè)鄰接矩陣表示該圖。略去結(jié)點(diǎn)標(biāo)定次序的任意性，取任意一個(gè)鄰接矩陣表示該圖。 對(duì)有向圖來(lái)說(shuō)，鄰接矩陣對(duì)有向圖來(lái)說(shuō)，鄰接矩陣A(G)的第的第i行行1的個(gè)數(shù)是的個(gè)數(shù)是vi的出的出度，度， 第第j列

58、列1的個(gè)數(shù)是的個(gè)數(shù)是vj的入度。的入度。 零圖的鄰接矩陣的元素全為零，叫做零矩陣。反過(guò)來(lái)，零圖的鄰接矩陣的元素全為零，叫做零矩陣。反過(guò)來(lái)，如果一個(gè)圖的鄰接矩陣是零矩陣，則此圖一定是零圖。如果一個(gè)圖的鄰接矩陣是零矩陣，則此圖一定是零圖。第七章：圖論第七章：圖論【定理定理7.3.1】設(shè)設(shè)A(G)是圖是圖G的鄰接矩陣，的鄰接矩陣，A(G)k=A(G)A(G)k-1，A(G)k的第的第i行，第行，第j列元素列元素 等于從等于從vi到到vj長(zhǎng)度為長(zhǎng)度為k的路的條數(shù)。的路的條數(shù)。其中其中 為為vi到自身長(zhǎng)度為到自身長(zhǎng)度為k的回路數(shù)。的回路數(shù)。 推論推論 設(shè)設(shè)G= V,E 是是n階簡(jiǎn)單有向圖，階簡(jiǎn)單有向圖，

59、A是有向圖是有向圖G的鄰接的鄰接矩陣，矩陣，Bk=AA2Ak，Bk=( )nn，則，則 是是G中由中由vi到到vj長(zhǎng)長(zhǎng)度小于等于度小于等于k的路的條數(shù)。的路的條數(shù)。 是是G中長(zhǎng)度小于等于中長(zhǎng)度小于等于k的路的的路的總條數(shù)?？倵l數(shù)。 是是G中長(zhǎng)度小于等于中長(zhǎng)度小于等于k的回路數(shù)。的回路數(shù)?！纠纠?.3.1】 設(shè)設(shè)G= V,E 為簡(jiǎn)單有向圖，圖形如圖為簡(jiǎn)單有向圖，圖形如圖7.16，寫(xiě)出，寫(xiě)出G的鄰接矩陣的鄰接矩陣A，算出，算出A2，A3，A4且確定且確定v1到到v2有多少條長(zhǎng)度為有多少條長(zhǎng)度為3的路的路? v1到到v3有多少條長(zhǎng)度為有多少條長(zhǎng)度為2的路的路? v2到自身長(zhǎng)度為到自身長(zhǎng)度為3和長(zhǎng)度

60、和長(zhǎng)度為為4的回路各多少條的回路各多少條?kijakiiakijb ninjkijb11nikiib1kijb第七章：圖論第七章：圖論 解：解：鄰接矩陣鄰接矩陣A和和A2，A3，A4如下：如下：0100010000000100010100010A 10000010000010100020001012A第七章：圖論第七章：圖論01000100000002000202000203A10000010000020200040002024A =2，所以，所以v1到到v2長(zhǎng)度為長(zhǎng)度為3的路有的路有2條，它們分別是：條，它們分別是：v1v2v1v2和和v1v2v3v2。 =1，所以，所以v1到到v3長(zhǎng)度為長(zhǎng)