第七章 圖論第一節(jié). 圖的基本概念定義7-1.1 一個(gè)圖是一個(gè)三元組 .

1、第七章第七章 圖論圖論第一節(jié)第一節(jié). 圖的基本概念圖的基本概念定義定義7-1.1 一個(gè)圖是一個(gè)三元組一個(gè)圖是一個(gè)三元組 ,其中其中V(G)V(G)是一個(gè)是一個(gè)非空的非空的結(jié)點(diǎn)集合結(jié)點(diǎn)集合, ,E(G)E(G)是邊集合是邊集合, , G是從邊集合到結(jié)點(diǎn)無(wú)序偶是從邊集合到結(jié)點(diǎn)無(wú)序偶( (有序偶有序偶) )集合上的映集合上的映射射. .注注:1):1)圖也可簡(jiǎn)記為圖也可簡(jiǎn)記為G=,G=,這里這里V V是結(jié)點(diǎn)集是結(jié)點(diǎn)集,E,E是是 邊集邊集. . 2) 2)圖可以用一個(gè)具體的圖形來(lái)表示圖可以用一個(gè)具體的圖形來(lái)表示, ,也可以用也可以用 一個(gè)抽象的三元組來(lái)表示一個(gè)抽象的三元組來(lái)表示. . 例例.用三元組

2、給出圖用三元組給出圖G=如下如下: : V(G)=a,b,c,d, V(G)=a,b,c,d, E(G)= E(G)=e1, ,e2, ,e3, ,e4, ,e5, ,e6 G( (e1)=(a,b),)=(a,b),G( (e2)=(a,c),)=(a,c),G( (e3)=(b,d),)=(b,d),G( (e4)=(b,c),)=(b,c),G( (e5)=(d,c),)=(d,c),G( (e6)=(a,d).)=(a,d). 它的圖形如下圖它的圖形如下圖( (a)a)或或( (b)b)所示所示: : a a a a b d b d b d b d c c c c (a) (b) (a

3、) (b) 定義定義: 1)無(wú)序偶和有序偶無(wú)序偶和有序偶;無(wú)向邊和有向邊無(wú)向邊和有向邊; 2)有向圖有向圖;無(wú)向圖無(wú)向圖;混合圖混合圖. 注注:今后我們不討論混合圖今后我們不討論混合圖,而只討論有向圖和無(wú)而只討論有向圖和無(wú) 向圖向圖. 下圖中的下圖中的(a)和和(b)分別是有向圖和混合圖的例子分別是有向圖和混合圖的例子: (a) (b) 定義定義: 鄰接點(diǎn)鄰接點(diǎn):由一條有向或無(wú)向邊連接的兩個(gè)結(jié)點(diǎn)由一條有向或無(wú)向邊連接的兩個(gè)結(jié)點(diǎn). 鄰接邊鄰接邊:連接同一結(jié)點(diǎn)的兩條邊連接同一結(jié)點(diǎn)的兩條邊. 孤立結(jié)點(diǎn)孤立結(jié)點(diǎn):不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn). 自回路自回路(環(huán)環(huán)):連接同一結(jié)點(diǎn)的邊

4、連接同一結(jié)點(diǎn)的邊. 零圖零圖:僅有若干個(gè)孤立結(jié)點(diǎn)而沒(méi)有邊的圖僅有若干個(gè)孤立結(jié)點(diǎn)而沒(méi)有邊的圖. 平凡圖平凡圖:僅有一個(gè)孤立結(jié)點(diǎn)的圖僅有一個(gè)孤立結(jié)點(diǎn)的圖. 注注:環(huán)既可以看作是有向邊環(huán)既可以看作是有向邊,也可以看作是無(wú)向邊也可以看作是無(wú)向邊. 定義定義7-1.2(結(jié)點(diǎn)的度數(shù)結(jié)點(diǎn)的度數(shù)deg(v v) 與結(jié)點(diǎn)與結(jié)點(diǎn) v v 關(guān)聯(lián)的邊數(shù)稱為該結(jié)點(diǎn)的度數(shù)關(guān)聯(lián)的邊數(shù)稱為該結(jié)點(diǎn)的度數(shù),記記 為為deg(v v). 定義定義:圖的最大度圖的最大度(G)和和最小度最小度(G). 定理定理7-1.1每個(gè)圖中每個(gè)圖中,所有結(jié)點(diǎn)的度數(shù)之和恰好等所有結(jié)點(diǎn)的度數(shù)之和恰好等 于該圖的邊數(shù)的兩倍于該圖的邊數(shù)的兩倍,即有即有

5、deg(v v)=2|E|. 利用這一定理以及奇數(shù)和偶數(shù)的基本性質(zhì)利用這一定理以及奇數(shù)和偶數(shù)的基本性質(zhì),不難不難證明下面有用的結(jié)果證明下面有用的結(jié)果: 定理定理7-1.2在任何圖中在任何圖中,度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)必度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)必 為偶數(shù)為偶數(shù). 定義定義7-1.3(有向圖中結(jié)點(diǎn)的出度有向圖中結(jié)點(diǎn)的出度deg+(v v)和入度和入度 deg-(v v) 顯然顯然,在任何有向圖中在任何有向圖中,對(duì)任一結(jié)點(diǎn)對(duì)任一結(jié)點(diǎn)v v都有都有 deg+(v v)+ deg-(v v)= deg(v v). 定理定理7-1.3 在任何有向圖中在任何有向圖中,所有結(jié)點(diǎn)的入度之和所有結(jié)點(diǎn)的入度之和 必等于它們

6、的出度之和必等于它們的出度之和. 證明證明:因?yàn)橛邢驁D中的每一條有向邊都恰好對(duì)應(yīng)因?yàn)橛邢驁D中的每一條有向邊都恰好對(duì)應(yīng) 一個(gè)出度和一個(gè)入度一個(gè)出度和一個(gè)入度.故所有結(jié)點(diǎn)的出度之故所有結(jié)點(diǎn)的出度之 和恰好等于有向邊的總數(shù)和恰好等于有向邊的總數(shù).同樣地同樣地, 所有結(jié)所有結(jié) 點(diǎn)的入度之和恰好也等于有向邊的總數(shù)點(diǎn)的入度之和恰好也等于有向邊的總數(shù).因因 此它們相等此它們相等. 定義定義7-1.4(平行邊平行邊,多重圖多重圖,簡(jiǎn)單圖簡(jiǎn)單圖) 平行邊平行邊:連接同一對(duì)結(jié)點(diǎn)如有多于一條邊連接同一對(duì)結(jié)點(diǎn)如有多于一條邊,則稱該則稱該 圖有平行邊圖有平行邊. 多重圖多重圖:有平行邊的圖有平行邊的圖. 簡(jiǎn)單圖簡(jiǎn)單圖:

7、沒(méi)有平行邊沒(méi)有平行邊,也沒(méi)有環(huán)的圖也沒(méi)有環(huán)的圖. 定義定義7-1.5(完全圖完全圖)每對(duì)結(jié)點(diǎn)間都恰有一條邊相連每對(duì)結(jié)點(diǎn)間都恰有一條邊相連 的圖稱為完全圖的圖稱為完全圖. 有有n個(gè)結(jié)點(diǎn)的完全圖記為個(gè)結(jié)點(diǎn)的完全圖記為 Kn. 定理定理7-1.4 n個(gè)結(jié)點(diǎn)的無(wú)向完全圖個(gè)結(jié)點(diǎn)的無(wú)向完全圖 Kn的邊數(shù)為的邊數(shù)為 |E|=(1/2)n(n-1). 證明證明:根據(jù)完全圖的定義根據(jù)完全圖的定義,它的任意兩個(gè)結(jié)點(diǎn)間都它的任意兩個(gè)結(jié)點(diǎn)間都 恰好有一條邊相連恰好有一條邊相連,而從個(gè)結(jié)點(diǎn)中任取兩點(diǎn)而從個(gè)結(jié)點(diǎn)中任取兩點(diǎn) 的所有組合數(shù)等于的所有組合數(shù)等于 = (1/2)n(n-1). 這正是我們所要證明的這正是我們所要證

8、明的. 定義定義7-1.6(相對(duì)完全圖的補(bǔ)圖相對(duì)完全圖的補(bǔ)圖)給定簡(jiǎn)單圖給定簡(jiǎn)單圖G,由由G 中所有結(jié)點(diǎn)和所有能使中所有結(jié)點(diǎn)和所有能使G成為完全圖的添加邊組成為完全圖的添加邊組成的圖稱為成的圖稱為G的相對(duì)于完全圖的補(bǔ)圖的相對(duì)于完全圖的補(bǔ)圖,或簡(jiǎn)稱為或簡(jiǎn)稱為G的補(bǔ)圖的補(bǔ)圖,記為記為 .例如下面兩圖互為補(bǔ)圖例如下面兩圖互為補(bǔ)圖.2nCG 定義定義7-1.7(子圖子圖,生成子圖生成子圖)給定圖給定圖G=,如果如果有圖有圖G=,使得使得E E, V V,則稱則稱G是是G的的子圖子圖. 如果子圖如果子圖G還包含還包含G的所有結(jié)點(diǎn)的所有結(jié)點(diǎn),則子圖則子圖G稱為稱為G的生成子圖的生成子圖. 定義定義(相對(duì)于

9、一個(gè)圖的補(bǔ)圖相對(duì)于一個(gè)圖的補(bǔ)圖)設(shè)圖設(shè)圖G=是圖是圖G=,的子圖的子圖. 若對(duì)另外一個(gè)圖若對(duì)另外一個(gè)圖G=有有E= E-E,且且V中僅包含中僅包含E的邊所關(guān)聯(lián)的結(jié)點(diǎn)的邊所關(guān)聯(lián)的結(jié)點(diǎn).則稱則稱G是的子圖是的子圖G關(guān)于圖關(guān)于圖G的補(bǔ)圖的補(bǔ)圖. 例如例如:下圖中下圖中(b)和和(c)都是都是(a)的子圖的子圖;(c)是是(b)相對(duì)于相對(duì)于(a)的補(bǔ)圖的補(bǔ)圖,但但(b)不是不是(c)相對(duì)于相對(duì)于(a)的補(bǔ)圖的補(bǔ)圖. (a) (b) (c) 例例:下圖中下圖中,(b)和和(c)都是都是(a)的子圖的子圖,且它們都是且它們都是(a)的生成子圖的生成子圖;又又(b)是是(c)的相對(duì)于的相對(duì)于(a)的補(bǔ)圖的補(bǔ)

10、圖,且且(c)也是也是(b)的相對(duì)于的相對(duì)于(a)的補(bǔ)圖的補(bǔ)圖.此外此外,(b)還和還和(c)互為互為關(guān)于完全圖關(guān)于完全圖(這里的完全圖指的是這里的完全圖指的是K4)的補(bǔ)圖的補(bǔ)圖. (a) K4 (b) (c) 定義定義7-1.9(圖的同構(gòu)圖的同構(gòu))假設(shè)給定兩個(gè)圖假設(shè)給定兩個(gè)圖G=和和 G=,如果存在它們的結(jié)點(diǎn)集如果存在它們的結(jié)點(diǎn)集V與與V之之 間的一個(gè)一一映射間的一個(gè)一一映射g g: 使得使得 (或者或者 )是是G的一條邊的一條邊,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) (或者或者 )是是G的一條邊的一條邊,則稱圖則稱圖G與與 圖圖G是兩個(gè)同構(gòu)的圖是兩個(gè)同構(gòu)的圖,記為記為G G. 容易看出，同構(gòu)的圖有如下一些性質(zhì)

11、：容易看出，同構(gòu)的圖有如下一些性質(zhì)： 1）結(jié)點(diǎn)數(shù)目相同；）結(jié)點(diǎn)數(shù)目相同； 2）邊數(shù)相等；）邊數(shù)相等； 3）度數(shù)相同的結(jié)點(diǎn)個(gè)數(shù)相等。）度數(shù)相同的結(jié)點(diǎn)個(gè)數(shù)相等。 但要注意的是：以上三個(gè)條件僅僅是兩個(gè)圖同構(gòu)但要注意的是：以上三個(gè)條件僅僅是兩個(gè)圖同構(gòu)的必要條件，而非充分條件。的必要條件，而非充分條件。iivv ),(jivve jivve,)(),(jivgvge )(),(jivgvge 例子：例子： 1）下面兩個(gè)無(wú)向圖是同構(gòu)的。）下面兩個(gè)無(wú)向圖是同構(gòu)的。 2）下面兩個(gè)有向圖也是同構(gòu)的。）下面兩個(gè)有向圖也是同構(gòu)的。 3)下面兩個(gè)圖中雖然結(jié)點(diǎn)個(gè)數(shù)下面兩個(gè)圖中雖然結(jié)點(diǎn)個(gè)數(shù)、邊數(shù)以及度數(shù)相、邊數(shù)以及度數(shù)相

12、同的結(jié)點(diǎn)個(gè)數(shù)都相同同的結(jié)點(diǎn)個(gè)數(shù)都相同, ,但是它們并不是同構(gòu)的圖但是它們并不是同構(gòu)的圖. . 第二節(jié)第二節(jié). 路路, 回路與連通性回路與連通性 定義定義7-2.1(路路,跡跡,通路和圈通路和圈) 給定圖給定圖G=,設(shè)設(shè)v v0,v v1,v vn V, e e1, e e2, e en E,其中其中e ei是關(guān)聯(lián)于結(jié)點(diǎn)是關(guān)聯(lián)于結(jié)點(diǎn)v vi-1和和v vi的邊的邊,我們把由結(jié)我們把由結(jié)點(diǎn)和邊組成的交替序列點(diǎn)和邊組成的交替序列 v v0 e e1v v1e e2 e env vn 稱為是從點(diǎn)稱為是從點(diǎn)v v0到點(diǎn)到點(diǎn)v vn的一條的一條路路. 這條路中邊的條這條路中邊的條 數(shù)稱為這條數(shù)稱為這條路的

13、長(zhǎng)度路的長(zhǎng)度.當(dāng)當(dāng)v v0=v vn時(shí)時(shí),稱這條路為一條稱這條路為一條 回路回路. 若一條路中所有的邊均不相同若一條路中所有的邊均不相同,稱之為稱之為跡跡.若若 這條路中所有的結(jié)點(diǎn)均不相同這條路中所有的結(jié)點(diǎn)均不相同,稱之為稱之為通路通路. 當(dāng)當(dāng)v v0=v vn而其余結(jié)點(diǎn)均不相同時(shí)而其余結(jié)點(diǎn)均不相同時(shí),稱之為稱之為圈圈. 例子例子. 在下面的圖中找出一條路在下面的圖中找出一條路,一條跡一條跡,一條通一條通 路和一個(gè)圈來(lái)路和一個(gè)圈來(lái). v v1 e e1 e e2 e e3 v v2 v v3 e e4 e e5 e e6 e e7 v v4 e e8 v v5 定理定理7-2.1在一個(gè)有在一個(gè)

14、有n個(gè)結(jié)點(diǎn)的圖中個(gè)結(jié)點(diǎn)的圖中, 如果從結(jié)點(diǎn)如果從結(jié)點(diǎn)v vj j到結(jié)點(diǎn)到結(jié)點(diǎn)v vk k存在一條路存在一條路,那么從結(jié)點(diǎn)那么從結(jié)點(diǎn)v vj j到結(jié)點(diǎn)到結(jié)點(diǎn)v vk k 必存在一條邊數(shù)至多為必存在一條邊數(shù)至多為n-1的路的路. 推論推論.在一個(gè)有在一個(gè)有n個(gè)結(jié)點(diǎn)的圖中個(gè)結(jié)點(diǎn)的圖中, 如果從結(jié)點(diǎn)如果從結(jié)點(diǎn)v vj j到到 結(jié)點(diǎn)結(jié)點(diǎn)v vk k存在一條路存在一條路,那么從結(jié)點(diǎn)那么從結(jié)點(diǎn)v vj j到結(jié)點(diǎn)到結(jié)點(diǎn)v vk k必存必存 在一條邊數(shù)至多為在一條邊數(shù)至多為n-1的通路的通路. 定義定義7-2.2(點(diǎn)的連通性點(diǎn)的連通性)設(shè)設(shè)G為無(wú)向圖為無(wú)向圖,若在結(jié)點(diǎn)若在結(jié)點(diǎn)v vj j 與結(jié)點(diǎn)與結(jié)點(diǎn)v vk

15、k之間存在一條之間存在一條,路則稱結(jié)點(diǎn)路則稱結(jié)點(diǎn)v vj j與結(jié)點(diǎn)與結(jié)點(diǎn)v vk k 是連通的是連通的. 注：不難證明，結(jié)點(diǎn)之間的連通性是結(jié)點(diǎn)集合注：不難證明，結(jié)點(diǎn)之間的連通性是結(jié)點(diǎn)集合V 上的一個(gè)等價(jià)關(guān)系，即它滿足自反性，對(duì)稱性和上的一個(gè)等價(jià)關(guān)系，即它滿足自反性，對(duì)稱性和 傳遞性。由此可以根據(jù)結(jié)點(diǎn)之間有無(wú)連通性來(lái)將傳遞性。由此可以根據(jù)結(jié)點(diǎn)之間有無(wú)連通性來(lái)將 結(jié)點(diǎn)集合進(jìn)行分類：把凡是連通的結(jié)點(diǎn)放在同一結(jié)點(diǎn)集合進(jìn)行分類：把凡是連通的結(jié)點(diǎn)放在同一 個(gè)類中。這樣得到的每個(gè)類中的所有結(jié)點(diǎn)和相應(yīng)個(gè)類中。這樣得到的每個(gè)類中的所有結(jié)點(diǎn)和相應(yīng)的邊作成的子圖稱為是原圖的一個(gè)的邊作成的子圖稱為是原圖的一個(gè)連通分支

16、連通分支。圖。圖G的連通分支的個(gè)數(shù)記為的連通分支的個(gè)數(shù)記為W(G)。例如，下面的例如，下面的圖有三個(gè)連通分支，即圖有三個(gè)連通分支，即W(G)=3。 定義定義7-2.3(連通圖連通圖)若圖若圖G只有一個(gè)連通分支只有一個(gè)連通分支,即有即有 W(G)=1,則稱它是一個(gè)連通圖則稱它是一個(gè)連通圖. 定義定義7-2.4(點(diǎn)割集點(diǎn)割集,割點(diǎn)割點(diǎn))設(shè)無(wú)向圖設(shè)無(wú)向圖G=為一連為一連 通圖通圖,若有點(diǎn)集若有點(diǎn)集V1 V,使得在圖中刪去了點(diǎn)集使得在圖中刪去了點(diǎn)集V1中中 所有的結(jié)點(diǎn)后所有的結(jié)點(diǎn)后,所得子圖是不連通的圖所得子圖是不連通的圖.而從圖中而從圖中刪刪 去點(diǎn)集去點(diǎn)集V1的任一真子集后的任一真子集后,得到的子圖

17、仍是連通圖得到的子圖仍是連通圖. 則稱點(diǎn)集則稱點(diǎn)集V1是圖是圖G的一個(gè)點(diǎn)割集的一個(gè)點(diǎn)割集.若點(diǎn)割集中恰只若點(diǎn)割集中恰只有一個(gè)結(jié)點(diǎn)有一個(gè)結(jié)點(diǎn),則稱它是該圖的一個(gè)割點(diǎn)則稱它是該圖的一個(gè)割點(diǎn). 定義定義7-2.5(邊割集邊割集,割邊割邊)設(shè)無(wú)向圖設(shè)無(wú)向圖G=為一為一 連通圖連通圖,若有邊集若有邊集E1 E,使得在圖中刪去了邊集使得在圖中刪去了邊集 E1中所有的邊后中所有的邊后,所得子圖是不連通的圖所得子圖是不連通的圖.而從圖而從圖 中刪去邊集中刪去邊集E1的任一真子集后的任一真子集后,得到的子圖仍是得到的子圖仍是連通圖連通圖.則稱邊集則稱邊集E1是圖是圖G的一個(gè)的一個(gè)邊割集邊割集.若邊割若邊割集中恰

18、只有一條邊集中恰只有一條邊,則稱它是該圖的一個(gè)則稱它是該圖的一個(gè)割邊割邊,也也稱為一個(gè)稱為一個(gè)橋橋. 定義定義(點(diǎn)連通度點(diǎn)連通度)設(shè)設(shè)G是一個(gè)圖，則定義是一個(gè)圖，則定義 k k(G)=min|V1|:V1是是G的點(diǎn)割集的點(diǎn)割集 為圖的為圖的點(diǎn)連通度點(diǎn)連通度(或或連通度連通度). 例例.對(duì)完全圖對(duì)完全圖Kp來(lái)說(shuō)來(lái)說(shuō),顯然有顯然有 k k(Kp)=p-1. 定義定義(邊連通度邊連通度)設(shè)設(shè)G是一個(gè)圖，則定義是一個(gè)圖，則定義 (G)=min|E1|:E1是是G的邊割集的邊割集 為圖的為圖的邊連通度邊連通度.對(duì)于對(duì)于平凡圖平凡圖，也即僅由一個(gè)孤，也即僅由一個(gè)孤立結(jié)點(diǎn)作成的圖立結(jié)點(diǎn)作成的圖G,可以規(guī)定有

19、可以規(guī)定有(G)=0.此外此外,對(duì)于對(duì)于任何不連通的圖任何不連通的圖G,也有也有(G)=0. 定理定理7-2.2 對(duì)任何一個(gè)圖對(duì)任何一個(gè)圖G有有 k k(G) (G) (G), 這里這里k k(G)是點(diǎn)連通度是點(diǎn)連通度,(G)是邊連通度是邊連通度,而而(G)是是圖的最小度圖的最小度. 證明證明 1）根據(jù)圖的最小度以及邊連通度的定義易見(jiàn)）根據(jù)圖的最小度以及邊連通度的定義易見(jiàn),不不 等式等式(G) (G)總是成立的總是成立的. 2)下面來(lái)證明不等式下面來(lái)證明不等式k k(G) (G). 情形一情形一.若若(G)=1,也即圖也即圖G有一條割邊有一條割邊,此時(shí)顯然也有此時(shí)顯然也有k k(G)=1(因?yàn)?/p>

20、只要把這條割邊的任一個(gè)端點(diǎn)刪去因?yàn)橹灰堰@條割邊的任一個(gè)端點(diǎn)刪去,該圖就該圖就一定成為不連通圖了一定成為不連通圖了),故結(jié)論已成立故結(jié)論已成立. 情形二情形二.若若(G)2,則可從圖中刪去某則可從圖中刪去某(G)條邊條邊,使之不連使之不連通通;然而若從那然而若從那(G)條邊中刪去條邊中刪去(G)-1條邊條邊,得到的圖仍得到的圖仍是連通的是連通的,且在這樣得到的子圖中恰有一個(gè)橋且在這樣得到的子圖中恰有一個(gè)橋e e=(u u,v v).對(duì)對(duì)于那于那(G)-1條邊中的每一條邊條邊中的每一條邊,都選取一個(gè)不同于都選取一個(gè)不同于u u和和v v的的結(jié)點(diǎn)結(jié)點(diǎn),把這些結(jié)點(diǎn)全部刪去把這些結(jié)點(diǎn)全部刪去,就至少刪

21、掉了圖中的就至少刪掉了圖中的(G)-1條邊條邊.如果這樣得到的圖是不連通圖如果這樣得到的圖是不連通圖,就有就有k k(G) (G)-1 (G);如果這樣得到的圖仍是連通圖如果這樣得到的圖仍是連通圖,則則e e仍然是橋仍然是橋,這時(shí)這時(shí)再刪去結(jié)點(diǎn)再刪去結(jié)點(diǎn)u u或者或者v v,就必然得到一個(gè)不連通的圖就必然得到一個(gè)不連通的圖,故有故有k k(G) (G).這就完成了我們的證明這就完成了我們的證明. (注注)下面的圖中容易看出有下面的圖中容易看出有 k k(G)=2， (G)=3， (G)=4， 這對(duì)定理這對(duì)定理7-2.2的結(jié)論也給出一個(gè)例證的結(jié)論也給出一個(gè)例證. 定理定理7-2.3一個(gè)無(wú)向連通圖

22、一個(gè)無(wú)向連通圖G中的結(jié)點(diǎn)中的結(jié)點(diǎn)v v是圖是圖G的割點(diǎn)的的割點(diǎn)的 充分必要條件是充分必要條件是:存在兩個(gè)結(jié)點(diǎn)存在兩個(gè)結(jié)點(diǎn)u u和和w w,使得連接結(jié)點(diǎn)使得連接結(jié)點(diǎn)u u 和和w w的每一條路都通過(guò)結(jié)點(diǎn)的每一條路都通過(guò)結(jié)點(diǎn)v v. 證明證明:1)必要性必要性.設(shè)結(jié)點(diǎn)設(shè)結(jié)點(diǎn)v v是圖是圖G的割點(diǎn)的割點(diǎn).那么在圖那么在圖G中刪去中刪去 該點(diǎn)就得到一個(gè)不連通的圖該點(diǎn)就得到一個(gè)不連通的圖F,于是于是F至少有兩個(gè)連通分至少有兩個(gè)連通分支支F1和和F2,分別從分別從F1和和F2中各任取一點(diǎn)中各任取一點(diǎn)u u和和w w,由于原圖由于原圖G 是連通的是連通的,而在去掉割點(diǎn)而在去掉割點(diǎn)v v后得到的圖后得到的圖F

23、中它們不再連通中它們不再連通, 這就表明在圖這就表明在圖G中連接這兩個(gè)結(jié)點(diǎn)的任一條路必定都經(jīng)中連接這兩個(gè)結(jié)點(diǎn)的任一條路必定都經(jīng) 過(guò)結(jié)點(diǎn)過(guò)結(jié)點(diǎn)v v. 2)充分性充分性.設(shè)圖設(shè)圖G中存在兩個(gè)結(jié)點(diǎn)中存在兩個(gè)結(jié)點(diǎn)u u和和w w,使得連接使得連接 結(jié)點(diǎn)結(jié)點(diǎn)u u和和w w的每一條路都通過(guò)結(jié)點(diǎn)的每一條路都通過(guò)結(jié)點(diǎn)v v.那么顯然那么顯然,只要去掉只要去掉 結(jié)點(diǎn)結(jié)點(diǎn)v v,u u和和w w這兩個(gè)結(jié)點(diǎn)就會(huì)變成不連通的這兩個(gè)結(jié)點(diǎn)就會(huì)變成不連通的,從而圖從而圖G也也 就變成不連通的圖就變成不連通的圖.這就證明了結(jié)點(diǎn)這就證明了結(jié)點(diǎn)v v必為圖的割點(diǎn)必為圖的割點(diǎn). 注意注意: 1)無(wú)向圖的連通性不能直接推廣到有向

24、圖無(wú)向圖的連通性不能直接推廣到有向圖. 2)在有向圖中可以定義在有向圖中可以定義可達(dá)性可達(dá)性如下如下: 如果從結(jié)點(diǎn)如果從結(jié)點(diǎn)u u到結(jié)點(diǎn)到結(jié)點(diǎn)v v有一條有一條(有向的有向的)路相通路相通, 則稱從點(diǎn)則稱從點(diǎn)u u到點(diǎn)到點(diǎn)v v可達(dá)可達(dá). 注意注意,結(jié)點(diǎn)間的可達(dá)性是自反的和傳遞的結(jié)點(diǎn)間的可達(dá)性是自反的和傳遞的,但一但一 般不是對(duì)稱的般不是對(duì)稱的. 3)如果在一個(gè)有向圖中從點(diǎn)如果在一個(gè)有向圖中從點(diǎn)u u到點(diǎn)到點(diǎn)v v可達(dá)可達(dá),則稱從則稱從 點(diǎn)點(diǎn)u u到點(diǎn)到點(diǎn)v v的所有的所有(有向的有向的)路中最短的那條路的路中最短的那條路的 長(zhǎng)度為結(jié)點(diǎn)長(zhǎng)度為結(jié)點(diǎn)u u到到v v的距離的距離,記為記為d d.

25、如果從結(jié)點(diǎn)如果從結(jié)點(diǎn)u u到到v v不可達(dá)不可達(dá),則記則記d d=. 注意注意,當(dāng)從點(diǎn)當(dāng)從點(diǎn)u u到點(diǎn)到點(diǎn)v v可達(dá)時(shí)可達(dá)時(shí),從點(diǎn)從點(diǎn)v v到點(diǎn)到點(diǎn)u u不一定不一定 也可達(dá)也可達(dá);即使從點(diǎn)即使從點(diǎn)v v到點(diǎn)到點(diǎn)u u也可達(dá)也可達(dá),一般也不一定一般也不一定 有有d d=d d. 定義定義(無(wú)向圖的直徑無(wú)向圖的直徑)設(shè)設(shè)G=是一個(gè)無(wú)向圖是一個(gè)無(wú)向圖,稱稱 D=maxd d,u u,v v V 為圖為圖G的直徑的直徑. 第三節(jié)第三節(jié). 圖的矩陣表示圖的矩陣表示 定義定義7-3.1(圖的鄰接矩陣圖的鄰接矩陣)設(shè)設(shè)G=是一個(gè)簡(jiǎn)單是一個(gè)簡(jiǎn)單 圖圖(即沒(méi)有平行邊和環(huán)的圖即沒(méi)有平行邊和環(huán)的圖),它有它有n個(gè)

26、結(jié)點(diǎn)個(gè)結(jié)點(diǎn) V=v v1,v v2,.,v vn, 我們稱我們稱n階方陣階方陣A(G)=(aij)為為G的鄰接矩陣的鄰接矩陣,這里這里 aij=1(當(dāng)當(dāng)v vi鄰接鄰接v vj時(shí)時(shí)), aij=0(當(dāng)當(dāng)v vi不鄰接不鄰接v vj時(shí)時(shí)). 例子例子.下圖下圖(a)的鄰接矩陣如的鄰接矩陣如(b)所示所示. v v1 v v2 v v5 A(G)= v v3 v v4 (a) (b)0110010011010110010111110 注注:1)無(wú)向圖無(wú)向圖的鄰接矩陣必為的鄰接矩陣必為對(duì)稱陣對(duì)稱陣;而而有向圖有向圖的鄰接矩的鄰接矩 陣一般不一定是對(duì)稱陣陣一般不一定是對(duì)稱陣;顯然顯然,一個(gè)圖為一個(gè)圖為

27、零圖零圖(全由全由 孤立結(jié)點(diǎn)構(gòu)成的圖孤立結(jié)點(diǎn)構(gòu)成的圖)的充分必要條件是它的鄰接矩的充分必要條件是它的鄰接矩 陣必為陣必為零陣零陣. 2)有向圖有向圖(無(wú)向圖無(wú)向圖)中中鄰接矩陣中第鄰接矩陣中第i i行元素之和恰為行元素之和恰為 結(jié)點(diǎn)結(jié)點(diǎn)v vi i的的出度出度(度度). 3)圖的鄰接矩陣一般說(shuō)來(lái)與結(jié)點(diǎn)的書(shū)寫(xiě)次序有關(guān)圖的鄰接矩陣一般說(shuō)來(lái)與結(jié)點(diǎn)的書(shū)寫(xiě)次序有關(guān). 4)給定兩個(gè)同階矩陣給定兩個(gè)同階矩陣,如果能通過(guò)對(duì)其中任一矩陣的如果能通過(guò)對(duì)其中任一矩陣的 某些行作次序調(diào)換某些行作次序調(diào)換,同時(shí)對(duì)相應(yīng)的列作同樣的調(diào)換同時(shí)對(duì)相應(yīng)的列作同樣的調(diào)換, 就可將它變成另一個(gè)矩陣就可將它變成另一個(gè)矩陣,就稱這兩個(gè)矩

28、陣是彼此就稱這兩個(gè)矩陣是彼此 置換等價(jià)的矩陣置換等價(jià)的矩陣.顯然顯然,從同一個(gè)圖作出的任意兩個(gè)從同一個(gè)圖作出的任意兩個(gè) 鄰接矩陣一定是置換等價(jià)的矩陣鄰接矩陣一定是置換等價(jià)的矩陣. 問(wèn)題問(wèn)題:怎樣計(jì)算圖中從一個(gè)結(jié)點(diǎn)怎樣計(jì)算圖中從一個(gè)結(jié)點(diǎn)v vi i到另一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn) v vj j的長(zhǎng)度為的長(zhǎng)度為k k的路的條數(shù)的路的條數(shù)? 定理定理7-3.1設(shè)給定圖設(shè)給定圖G和它的鄰接矩陣和它的鄰接矩陣A(G),用矩陣乘法用矩陣乘法 計(jì)算出鄰接矩陣計(jì)算出鄰接矩陣A(G)的的k k次冪次冪Ak k(G),則矩陣則矩陣Ak k(G)中第中第I I 行第行第j j列元素列元素bij ij的值即為圖的值即為圖G中

29、中從結(jié)點(diǎn)從結(jié)點(diǎn)v vi i到結(jié)點(diǎn)到結(jié)點(diǎn)v vj j的長(zhǎng)的長(zhǎng) 度為度為k k的路的條數(shù)的路的條數(shù). 例例1.給出圖給出圖G(見(jiàn)下圖見(jiàn)下圖(a),要求其中要求其中(1)從結(jié)點(diǎn)從結(jié)點(diǎn)v v1到結(jié)點(diǎn)到結(jié)點(diǎn)v v2的的長(zhǎng)度為長(zhǎng)度為3的路的條數(shù)的路的條數(shù);(2)從結(jié)點(diǎn)從結(jié)點(diǎn)v v2到結(jié)點(diǎn)到結(jié)點(diǎn)v v2的長(zhǎng)度為的長(zhǎng)度為3以及以及長(zhǎng)度為長(zhǎng)度為4的回路的條數(shù)的回路的條數(shù). 解解:容易算出此圖的鄰接矩陣容易算出此圖的鄰接矩陣A如如(b)所示所示. v v5 v v1 v v2 A= v v4 (a) v v3 (b)0110000000000100010100010 計(jì)算給出計(jì)算給出 A2= A3= A4 = 結(jié)

30、論結(jié)論:(1)從結(jié)點(diǎn)從結(jié)點(diǎn)v v1到結(jié)點(diǎn)到結(jié)點(diǎn)v v2有有2條長(zhǎng)度為條長(zhǎng)度為3的路的路. (2)從結(jié)點(diǎn)從結(jié)點(diǎn)v v2到結(jié)點(diǎn)到結(jié)點(diǎn)v v2沒(méi)有長(zhǎng)度為沒(méi)有長(zhǎng)度為3的回路的回路. (3)從結(jié)點(diǎn)從結(jié)點(diǎn)v v2到結(jié)點(diǎn)到結(jié)點(diǎn)v v2有有4條長(zhǎng)度為條長(zhǎng)度為4的回路的回路.100100000000101000200010110010000000020200040002020110000000000200020200020 定義定義7-3.2(有向圖的可達(dá)性矩陣有向圖的可達(dá)性矩陣)令令G是一個(gè)簡(jiǎn)單是一個(gè)簡(jiǎn)單 有向圖有向圖,其結(jié)點(diǎn)數(shù)為其結(jié)點(diǎn)數(shù)為|V|=n,并設(shè)已將圖的所有結(jié)點(diǎn)并設(shè)已將圖的所有結(jié)點(diǎn) 進(jìn)行了編序進(jìn)行了

31、編序: V=v v1,v v2,.,v vn.則稱如下定義的則稱如下定義的n階階 方陣方陣P=(p pij)為圖為圖G的可達(dá)性矩陣的可達(dá)性矩陣,這里這里 p pij=1 (如果從到至少有一條路如果從到至少有一條路)或者或者 p pij=0 (如果從到不存在路如果從到不存在路). 注注:可達(dá)性矩陣的概念也容易推廣到無(wú)向圖中可達(dá)性矩陣的概念也容易推廣到無(wú)向圖中,只只 要在無(wú)向圖中將每條無(wú)向邊改成兩條有向邊要在無(wú)向圖中將每條無(wú)向邊改成兩條有向邊 就行了就行了. 問(wèn)題問(wèn)題:怎樣從圖的鄰接矩陣求出其可達(dá)矩陣呢怎樣從圖的鄰接矩陣求出其可達(dá)矩陣呢? 解答解答:設(shè)設(shè)n階矩陣階矩陣A是圖是圖G的鄰接矩陣的鄰接矩

32、陣,用矩陣乘法用矩陣乘法 依次算出依次算出A2,A3,.,An,然后計(jì)算出矩陣然后計(jì)算出矩陣 B=A+A2 +A3+.+An, 再在矩陣再在矩陣B中將所有的非零元素都換成數(shù)中將所有的非零元素都換成數(shù)1;而而B(niǎo)中為零的元素中為零的元素仍仍保持?jǐn)?shù)零不動(dòng)保持?jǐn)?shù)零不動(dòng),這樣得到的矩陣這樣得到的矩陣K就是圖就是圖G的可達(dá)性矩陣的可達(dá)性矩陣. 例子例子.設(shè)圖設(shè)圖G的鄰接矩陣是的鄰接矩陣是 A= 求出它的可達(dá)性矩陣來(lái)求出它的可達(dá)性矩陣來(lái).0001101111000010 解解:計(jì)算給出計(jì)算給出 A2= A3= A4= B= + + + = 0010111110121100110021221121101210

33、12323332221121001011111012110011002122112110121012323332221121000110111100001021237477645532431111111111111111 第四節(jié)第四節(jié). 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖 歐拉歐拉(L. Euler)與哥尼斯堡與哥尼斯堡(Knigberg)七橋問(wèn)題七橋問(wèn)題 C A B D C A B D 定義定義7-4.1(歐拉路與歐拉回路歐拉路與歐拉回路)設(shè)圖設(shè)圖G無(wú)孤立結(jié)點(diǎn)無(wú)孤立結(jié)點(diǎn), 若若G中存在一條路中存在一條路,它經(jīng)過(guò)圖它經(jīng)過(guò)圖G中每條邊一次且只中每條邊一次且只 經(jīng)過(guò)一次經(jīng)過(guò)一次,則稱這條路為一條

34、歐拉路則稱這條路為一條歐拉路;如果它還是如果它還是 一條回路一條回路,則稱它為一條歐拉回路則稱它為一條歐拉回路.我們稱有歐拉我們稱有歐拉回路存在的圖是一個(gè)歐拉圖回路存在的圖是一個(gè)歐拉圖. (注注)我們不討論有孤立點(diǎn)的圖中有無(wú)歐拉路或歐我們不討論有孤立點(diǎn)的圖中有無(wú)歐拉路或歐 拉回路存在的問(wèn)題拉回路存在的問(wèn)題. 定理定理7-4.1 設(shè)設(shè)G是一個(gè)無(wú)孤立結(jié)點(diǎn)的無(wú)向圖是一個(gè)無(wú)孤立結(jié)點(diǎn)的無(wú)向圖,那么那么 G中存在一條歐拉路中存在一條歐拉路,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G是連通的是連通的,且恰有且恰有 零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn). 例子例子(哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題).由于由于該圖中有該圖中有4個(gè)

35、奇結(jié)個(gè)奇結(jié) 點(diǎn)點(diǎn),從而該圖中必不存在歐拉路或歐拉回路從而該圖中必不存在歐拉路或歐拉回路. 有關(guān)一筆畫(huà)與多筆畫(huà)問(wèn)題的結(jié)論有關(guān)一筆畫(huà)與多筆畫(huà)問(wèn)題的結(jié)論: (1)無(wú)孤立結(jié)點(diǎn)的無(wú)向圖無(wú)孤立結(jié)點(diǎn)的無(wú)向圖G是一個(gè)一筆畫(huà)的充分必是一個(gè)一筆畫(huà)的充分必 要條件是要條件是:它是一個(gè)連通圖它是一個(gè)連通圖,且奇結(jié)點(diǎn)的個(gè)為且奇結(jié)點(diǎn)的個(gè)為0 或?yàn)榛驗(yàn)?. (2)設(shè)設(shè)G是一個(gè)連通無(wú)向圖是一個(gè)連通無(wú)向圖,它有它有2n個(gè)個(gè)(n1)奇結(jié)點(diǎn)奇結(jié)點(diǎn). 那么圖那么圖G必是一個(gè)必是一個(gè)n筆畫(huà)筆畫(huà),且最少是一個(gè)且最少是一個(gè)n筆畫(huà)筆畫(huà). 歐拉路及歐拉回路的概念在有向圖中的推廣歐拉路及歐拉回路的概念在有向圖中的推廣: 定義定義7-4.2(單向

36、歐拉路與單向歐拉回路單向歐拉路與單向歐拉回路)設(shè)設(shè)G是一是一 個(gè)有向圖個(gè)有向圖,如果如果G中存在一條有向路中存在一條有向路(有向回路有向回路),它它 經(jīng)過(guò)圖中每條有向邊恰好一次經(jīng)過(guò)圖中每條有向邊恰好一次,則稱它為一條單則稱它為一條單 向歐拉路向歐拉路(單向歐拉回路單向歐拉回路). 定理定理7-4.2設(shè)設(shè)G是一個(gè)有向圖是一個(gè)有向圖. (1)G中存在一條單向歐拉路的充分必要條件是中存在一條單向歐拉路的充分必要條件是: G是連通圖是連通圖,且除去兩個(gè)結(jié)點(diǎn)外且除去兩個(gè)結(jié)點(diǎn)外,其余每個(gè)結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn) 的入度等于出度的入度等于出度;在剩下的兩個(gè)結(jié)點(diǎn)中在剩下的兩個(gè)結(jié)點(diǎn)中,一個(gè)結(jié)一個(gè)結(jié) 點(diǎn)的入度比出度大點(diǎn)的

37、入度比出度大1,另一個(gè)結(jié)點(diǎn)的入度則比出另一個(gè)結(jié)點(diǎn)的入度則比出 度小度小1. (2) G中存在一條單向歐拉回路的充分必要條件中存在一條單向歐拉回路的充分必要條件 是是: G是連通圖是連通圖,且每個(gè)結(jié)點(diǎn)的入度等于出度且每個(gè)結(jié)點(diǎn)的入度等于出度. 定義定義7-4.3(哈密爾頓路與哈密爾頓回路哈密爾頓路與哈密爾頓回路)設(shè)設(shè)G是一是一 個(gè)圖個(gè)圖,若若G中存在一條路中存在一條路(回路回路),它經(jīng)過(guò)圖中每個(gè)結(jié)它經(jīng)過(guò)圖中每個(gè)結(jié) 點(diǎn)恰好一次點(diǎn)恰好一次(在回路的情形在回路的情形,起始點(diǎn)允許重復(fù)起始點(diǎn)允許重復(fù)),則則 稱它是一條哈密爾頓路稱它是一條哈密爾頓路(回路回路).我們稱有哈密爾頓我們稱有哈密爾頓回路存在的圖是

38、一個(gè)哈密爾頓圖回路存在的圖是一個(gè)哈密爾頓圖. 定理定理7-4.3(一個(gè)圖有哈密爾頓回路的必要條件一個(gè)圖有哈密爾頓回路的必要條件) 若圖若圖G=有哈密爾頓回路有哈密爾頓回路,則對(duì)結(jié)點(diǎn)集則對(duì)結(jié)點(diǎn)集V的每個(gè)非空子集的每個(gè)非空子集S均有不等式均有不等式 W(G-S)|S| 成立成立,其中其中W(G-S)表示子圖表示子圖G-S中的連通分支的中的連通分支的 個(gè)數(shù)個(gè)數(shù).(證明略證明略) 例子例子. (1)用定理用定理7-4.3可證下圖不是一個(gè)哈密爾頓圖可證下圖不是一個(gè)哈密爾頓圖. (2)但定理但定理7-4.3僅僅是個(gè)僅僅是個(gè) 必要條件必要條件,而非充分條而非充分條 件件.右圖右圖(Petersen圖圖)就就

39、 是一個(gè)滿足定理是一個(gè)滿足定理7-4.3 但并非哈密爾頓圖的例子但并非哈密爾頓圖的例子. 定理定理7-4.4(一個(gè)圖有哈密爾頓路的充分條件一個(gè)圖有哈密爾頓路的充分條件) 設(shè)設(shè)G是一個(gè)有是一個(gè)有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖.如果如果G中每中每 一對(duì)結(jié)點(diǎn)的度數(shù)之和都大于或等于一對(duì)結(jié)點(diǎn)的度數(shù)之和都大于或等于n-1,則則G中存中存 在一條哈密爾頓路在一條哈密爾頓路. (證明略證明略) 注意注意:此定理僅是充分條件此定理僅是充分條件 而非必要條件而非必要條件,例如右圖顯例如右圖顯 然是一個(gè)哈密爾頓圖然是一個(gè)哈密爾頓圖,當(dāng)然當(dāng)然 其中存在哈密爾頓路其中存在哈密爾頓路.然而然而 它的任一對(duì)結(jié)點(diǎn)度數(shù)之和它的

40、任一對(duì)結(jié)點(diǎn)度數(shù)之和 都小于該圖的結(jié)點(diǎn)總數(shù)都小于該圖的結(jié)點(diǎn)總數(shù). 例子例子. 證明下圖中不存在哈密爾頓路證明下圖中不存在哈密爾頓路. A B B B A A A A B B A B A A A B 定理定理7-4.5(一個(gè)圖有哈密爾頓路的充分條件一個(gè)圖有哈密爾頓路的充分條件) 設(shè)設(shè)G是一個(gè)有是一個(gè)有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖.如果如果G中每中每 一對(duì)結(jié)點(diǎn)的度數(shù)之和都大于或等于一對(duì)結(jié)點(diǎn)的度數(shù)之和都大于或等于n,則則G中存在中存在一條哈密爾頓回路一條哈密爾頓回路.(證明略證明略) 附附:哈密爾頓的周游世界問(wèn)題哈密爾頓的周游世界問(wèn)題(1859年年) 2 15 1 16 14 3 20 4 17 1

41、3 19 18 12 5 11 9 6 10 8 7 第五節(jié)第五節(jié). 平面圖平面圖 定義定義7-5.1(平面圖平面圖)設(shè)設(shè)G是一個(gè)無(wú)向圖是一個(gè)無(wú)向圖,如果能夠把如果能夠把 G的所有結(jié)點(diǎn)和邊畫(huà)在平面上的所有結(jié)點(diǎn)和邊畫(huà)在平面上,使得任何兩條邊除使得任何兩條邊除 了可能在結(jié)點(diǎn)處相交外了可能在結(jié)點(diǎn)處相交外,沒(méi)有其它的交點(diǎn)沒(méi)有其它的交點(diǎn).則稱它則稱它 是一個(gè)平面圖是一個(gè)平面圖.以下我們僅研究連通的平面圖以下我們僅研究連通的平面圖. 例子例子.下圖下圖(a)可以重新畫(huà)成可以重新畫(huà)成(b)的樣子的樣子,所以圖所以圖(a)仍仍 是平面圖是平面圖. (a) (b) 定義定義7-5.2(連通平面圖的面連通平面圖的

42、面,面的邊界面的邊界)設(shè)設(shè)G是一個(gè)是一個(gè) 連通平面圖連通平面圖.由圖由圖G中的邊所包圍的區(qū)域稱為圖中的邊所包圍的區(qū)域稱為圖G 的一個(gè)的一個(gè)面面(每個(gè)圖也包含一個(gè)無(wú)限的每個(gè)圖也包含一個(gè)無(wú)限的、位于圖的位于圖的外部的面外部的面),而包圍該面的各個(gè)邊就構(gòu)成這個(gè)而包圍該面的各個(gè)邊就構(gòu)成這個(gè)面的面的邊界邊界. r5 例子例子.右圖有右圖有6個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),9條邊條邊.它把平面它把平面 劃分成劃分成5個(gè)面?zhèn)€面:r1,r2,r3,r4和一個(gè)無(wú)限的和一個(gè)無(wú)限的 C 面面r5.其中的三個(gè)面其中的三個(gè)面r1,r2和和r4的邊界均的邊界均 A r4 由一條回路組成由一條回路組成,面面r3的邊界雖然并不的邊界雖然并不

43、Br2 F E 是一條回路是一條回路,但如果按照下面的方式但如果按照下面的方式 r1 r3 走完它的邊界走完它的邊界:CDEFEC(或順時(shí)針走或順時(shí)針走 D 也可也可),那么它的邊界也作成一條回路那么它的邊界也作成一條回路. 今后我們對(duì)面的邊界就規(guī)定為用這樣今后我們對(duì)面的邊界就規(guī)定為用這樣 的方式定義的一條回路的方式定義的一條回路. 定義定義(平面圖中面的次數(shù)平面圖中面的次數(shù))設(shè)設(shè)G是一個(gè)連通的平面是一個(gè)連通的平面 圖圖,按照上述約定按照上述約定,它把整個(gè)平面分成的每個(gè)面它把整個(gè)平面分成的每個(gè)面ri i 的邊界都是一條回路的邊界都是一條回路.稱該回路的長(zhǎng)度為這個(gè)面稱該回路的長(zhǎng)度為這個(gè)面的次數(shù)的

44、次數(shù),記為記為deg(ri i). 例如例如,在上面那個(gè)平面圖中有在上面那個(gè)平面圖中有 deg(r1)=3, deg(r2)=3, deg(r3)=5, deg(r4)=4, deg(r5)=3. 定理定理7-5.1 設(shè)設(shè)G是一個(gè)有限平面圖是一個(gè)有限平面圖,則它的所有面則它的所有面 的次數(shù)之和等于邊數(shù)的兩倍的次數(shù)之和等于邊數(shù)的兩倍. 定理定理7-5.2 設(shè)設(shè)G是一個(gè)非平凡的有限是一個(gè)非平凡的有限連通平面圖連通平面圖, 它有它有v v個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),e e條邊和條邊和r r個(gè)面?zhèn)€面,則有下述歐拉公式則有下述歐拉公式 成立成立: v v - e e + r r =2. 證明證明(對(duì)圖的邊數(shù)用歸納法對(duì)

45、圖的邊數(shù)用歸納法): (1)若若G只有一條邊只有一條邊,則則v v=2,e e=1,r r=1,結(jié)論顯然成立結(jié)論顯然成立. (2)(歸納假設(shè)歸納假設(shè))設(shè)當(dāng)設(shè)當(dāng)G有有k k條邊時(shí)結(jié)論成立條邊時(shí)結(jié)論成立: v vk k - e ek k + r rk k =2. (1) (3)現(xiàn)在設(shè)現(xiàn)在設(shè)G有有k k+1條邊條邊.即在原來(lái)有即在原來(lái)有k k條邊的連通圖條邊的連通圖G1中中 添加一條邊添加一條邊,使之仍為連通圖使之仍為連通圖(G1中的結(jié)點(diǎn)數(shù)中的結(jié)點(diǎn)數(shù)、邊數(shù)與面邊數(shù)與面 數(shù)滿足數(shù)滿足(1)式式).這只能有以下兩種情況這只能有以下兩種情況: 1)在在G1中增加一個(gè)新結(jié)點(diǎn)中增加一個(gè)新結(jié)點(diǎn) ,使之與使之與G

46、1中某個(gè)結(jié)點(diǎn)中某個(gè)結(jié)點(diǎn) 相連相連. 此時(shí)有此時(shí)有v vk k+1= v vk k+1,e ek k+1= e ek k+1,r rk k+1=r rk k,于是歐拉公式于是歐拉公式 v vk k+1 - e ek k+1 + r rk k+1 =2仍然成立仍然成立. 2)將將G1中某兩個(gè)結(jié)點(diǎn)中某兩個(gè)結(jié)點(diǎn) 與與 之間添加一條新的邊之間添加一條新的邊.此時(shí)有此時(shí)有 v vk k+1=v vk k, e ek k+1=e ek k+1, r rk k+1=r rk k(此處證明細(xì)節(jié)略去此處證明細(xì)節(jié)略去),于于 是此時(shí)歐拉公式是此時(shí)歐拉公式v vk k+1 - e ek k+1 + r rk k+1

47、=2仍然成立仍然成立. 定理定理7-5.3 設(shè)設(shè)G是一個(gè)有是一個(gè)有v v個(gè)結(jié)點(diǎn)和個(gè)結(jié)點(diǎn)和e e條邊的簡(jiǎn)單條邊的簡(jiǎn)單 連通平面圖連通平面圖.若若v v3,則有則有e e3v v-6. 證明證明:設(shè)設(shè)G有有r r個(gè)面?zhèn)€面. (1)若若v v3,e e3,則結(jié)論顯然成立則結(jié)論顯然成立. (2)若若v v3,e e4,一方面一方面由定理由定理7-5.1知知:G的所有面的所有面 的次數(shù)之和等于的次數(shù)之和等于2e e,另一方面另一方面,由于它是簡(jiǎn)單圖由于它是簡(jiǎn)單圖,故故 每個(gè)面的次數(shù)至少為每個(gè)面的次數(shù)至少為3,從而又有從而又有2e e3r r,即即r r(2/3)e e.將此不等式代入歐拉公式即得將此不等

48、式代入歐拉公式即得 2=v v-e e+r rv v-e e+(2/3)e e 2v v-(1/3)e e 63v v-e e e e3v v-6. 例子例子. (1)證明證明K5不是平面圖不是平面圖. 解解:在在K5中有中有v v=5個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), e e=10條邊條邊,因而對(duì)它有因而對(duì)它有 e e=109=3v v-6, 根據(jù)定理根據(jù)定理7-5.3,它不是平面圖它不是平面圖. K5 (2)證明證明K3,3不是平面圖不是平面圖. 解解:在在K3,3中有中有v v=6個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),e e=9條邊條邊,因而對(duì)它有因而對(duì)它有 e e=98=2v v-4, 故它不是平面圖故它不是平面圖. K3,3

49、定義定義7-5.3(在二度結(jié)點(diǎn)內(nèi)同構(gòu)的圖在二度結(jié)點(diǎn)內(nèi)同構(gòu)的圖)設(shè)設(shè)G1和和G2是是 兩個(gè)圖兩個(gè)圖,如果它們同構(gòu)如果它們同構(gòu),或者通過(guò)反復(fù)或者通過(guò)反復(fù)(有限次有限次)插插 入或除去度數(shù)為入或除去度數(shù)為2的結(jié)點(diǎn)后的結(jié)點(diǎn)后,能成為同構(gòu)的圖能成為同構(gòu)的圖,則稱則稱 它們是在二度結(jié)點(diǎn)內(nèi)同構(gòu)的圖它們是在二度結(jié)點(diǎn)內(nèi)同構(gòu)的圖. 插入和除去二度結(jié)點(diǎn)的簡(jiǎn)單例子插入和除去二度結(jié)點(diǎn)的簡(jiǎn)單例子: (a) (b) 定理定理7-5.4(Kuratowski定理定理) 一個(gè)圖是平面圖一個(gè)圖是平面圖,當(dāng)當(dāng) 且僅當(dāng)它不包含與且僅當(dāng)它不包含與K3,3或或K5在在2度結(jié)點(diǎn)內(nèi)同構(gòu)的度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖子圖.(證明略證明略) 第六節(jié)第六節(jié)

50、. 對(duì)偶圖與著色對(duì)偶圖與著色 定義定義7-6.1(對(duì)偶圖對(duì)偶圖)給定平面圖給定平面圖G=,設(shè)它有設(shè)它有n 個(gè)面?zhèn)€面F1,F2,Fn,若有另外一個(gè)圖若有另外一個(gè)圖G*=滿足滿足 如下三條件如下三條件,則稱圖則稱圖G*是圖是圖G的對(duì)偶圖的對(duì)偶圖: (a)對(duì)圖對(duì)圖G的每個(gè)面的每個(gè)面,G的內(nèi)部有且僅有一個(gè)結(jié)點(diǎn)的內(nèi)部有且僅有一個(gè)結(jié)點(diǎn) v v*i i G*. (b)對(duì)于圖對(duì)于圖G中任意兩個(gè)面中任意兩個(gè)面Fi i和和Fj j之間的每一條公之間的每一條公 共邊界共邊界e ek k,都存在一條邊都存在一條邊e e*k k G*,使得使得e e*k k =(v v*i i, v v*j j),且且e e*k k和

51、和e ek k相交相交. (c)當(dāng)且僅當(dāng)單獨(dú)一條邊當(dāng)且僅當(dāng)單獨(dú)一條邊e ek k構(gòu)成圖構(gòu)成圖G的某一個(gè)面的某一個(gè)面Fi i 的邊界時(shí)的邊界時(shí),(b)中與中與e ek k對(duì)應(yīng)的邊對(duì)應(yīng)的邊e e*k k =(v v*i i,v v*i i)是是 一個(gè)環(huán)一個(gè)環(huán),且且e e*k k和和e ek k相交相交. (注注)顯然顯然,若圖若圖G*是圖是圖G的對(duì)偶圖的對(duì)偶圖,那么圖那么圖G也是圖也是圖 G*的對(duì)偶圖的對(duì)偶圖,從而它們必是互為對(duì)偶的圖從而它們必是互為對(duì)偶的圖. 對(duì)偶圖的簡(jiǎn)單例子對(duì)偶圖的簡(jiǎn)單例子:下圖中實(shí)線和虛線作成的兩下圖中實(shí)線和虛線作成的兩個(gè)圖是互為對(duì)偶的圖個(gè)圖是互為對(duì)偶的圖. (注注)若圖若圖

52、G*與圖與圖G是互為對(duì)偶的圖是互為對(duì)偶的圖,那么那么,只要兩個(gè)只要兩個(gè) 圖中有一個(gè)圖是連通的平面圖圖中有一個(gè)圖是連通的平面圖,另一個(gè)圖必也是另一個(gè)圖必也是連通的平面圖連通的平面圖. 定義定義(自對(duì)偶圖自對(duì)偶圖)若圖若圖G的對(duì)偶圖恰與的對(duì)偶圖恰與G同構(gòu)同構(gòu),則稱則稱 圖圖G是一個(gè)自對(duì)偶圖是一個(gè)自對(duì)偶圖. 例子例子.由右圖容易看出由右圖容易看出, 完全圖完全圖K4就是一就是一 個(gè)自對(duì)偶圖個(gè)自對(duì)偶圖. (1)四色定理的歷史簡(jiǎn)介四色定理的歷史簡(jiǎn)介: 1)Francis Guthrie(1899,后成為位于開(kāi)普頓的南非大學(xué)后成為位于開(kāi)普頓的南非大學(xué) 數(shù)學(xué)教授數(shù)學(xué)教授):1850年前后提出四色猜想年前后提

53、出四色猜想. 2)Augustus de Morgan 1852年年10月月23日給日給William R. Hamilton爵士的信提出四色猜想爵士的信提出四色猜想. 3)A. Cayley先后于先后于1878年年6月月13日和日和1879年在倫敦?cái)?shù)學(xué)年在倫敦?cái)?shù)學(xué) 會(huì)的會(huì)議上以及英國(guó)皇家地理協(xié)會(huì)會(huì)報(bào)上兩次重新提會(huì)的會(huì)議上以及英國(guó)皇家地理協(xié)會(huì)會(huì)報(bào)上兩次重新提 出這一問(wèn)題出這一問(wèn)題. 4)A. B. Kempe和和G. Tait于于1879年給出第一個(gè)證明年給出第一個(gè)證明. 5)P. J. Heawood于于1890年指出了他們證明中的錯(cuò)誤年指出了他們證明中的錯(cuò)誤. 6)K. Appel, W.

54、 Haken和和J. Koch 于于1976年用計(jì)算機(jī)給年用計(jì)算機(jī)給 出完全的證明出完全的證明(發(fā)表的兩篇論文長(zhǎng)達(dá)發(fā)表的兩篇論文長(zhǎng)達(dá)139頁(yè)頁(yè), 在在Illinois 大學(xué)的計(jì)算機(jī)上共花去大學(xué)的計(jì)算機(jī)上共花去1200小時(shí)的計(jì)算機(jī)時(shí)間小時(shí)的計(jì)算機(jī)時(shí)間). 地圖的著色問(wèn)題與對(duì)偶圖的著色問(wèn)題之間的聯(lián)系地圖的著色問(wèn)題與對(duì)偶圖的著色問(wèn)題之間的聯(lián)系: (1)將將地圖的著色問(wèn)題轉(zhuǎn)化成對(duì)偶圖的著色問(wèn)題地圖的著色問(wèn)題轉(zhuǎn)化成對(duì)偶圖的著色問(wèn)題. (2)對(duì)偶圖的正常著色問(wèn)題對(duì)偶圖的正常著色問(wèn)題. 定義定義(圖的正常著色圖的正常著色)設(shè)設(shè)G是一個(gè)圖是一個(gè)圖,對(duì)它的每個(gè)結(jié)點(diǎn)指定對(duì)它的每個(gè)結(jié)點(diǎn)指定 一種顏色一種顏色,使得沒(méi)

55、有兩個(gè)鄰接的結(jié)點(diǎn)能有相同的顏色使得沒(méi)有兩個(gè)鄰接的結(jié)點(diǎn)能有相同的顏色,這這 樣的著色就稱為是圖樣的著色就稱為是圖G的一種正常的著色的一種正常的著色. 定義定義(n色圖和圖的著色數(shù)色圖和圖的著色數(shù))如果圖如果圖G在正常著色時(shí)用到在正常著色時(shí)用到n 種不同的顏色種不同的顏色,則稱該圖是一個(gè)則稱該圖是一個(gè)n-色的圖色的圖;對(duì)圖對(duì)圖G進(jìn)行正進(jìn)行正常著色所需的最少的顏色數(shù)稱為圖常著色所需的最少的顏色數(shù)稱為圖G的著色數(shù)的著色數(shù),記為記為 (G). 定理定理7-6.1 對(duì)有對(duì)有n個(gè)結(jié)點(diǎn)的完全圖個(gè)結(jié)點(diǎn)的完全圖Kn,有有 (Kn)=n. 定理定理7-6.3( 五色定理五色定理) 對(duì)任何平面圖對(duì)任何平面圖G, 有有

56、 (G)5. (證明略證明略) 第七節(jié)第七節(jié). 樹(shù)與生成樹(shù)樹(shù)與生成樹(shù) 定義定義7-7.1(樹(shù)與森林樹(shù)與森林) (1)一個(gè)連通且無(wú)回路的無(wú)向圖稱為樹(shù)一個(gè)連通且無(wú)回路的無(wú)向圖稱為樹(shù). (2)樹(shù)中度數(shù)樹(shù)中度數(shù)1為的結(jié)點(diǎn)稱為樹(shù)葉為的結(jié)點(diǎn)稱為樹(shù)葉. (3)樹(shù)中度數(shù)大于的結(jié)點(diǎn)稱為分枝點(diǎn)或內(nèi)點(diǎn)樹(shù)中度數(shù)大于的結(jié)點(diǎn)稱為分枝點(diǎn)或內(nèi)點(diǎn). (4)一個(gè)無(wú)回路的無(wú)向圖稱為森林一個(gè)無(wú)回路的無(wú)向圖稱為森林.顯然顯然,森林的每森林的每 個(gè)連通分支都是一棵樹(shù)個(gè)連通分支都是一棵樹(shù). 森林和樹(shù)的例子森林和樹(shù)的例子: 定理定理7-7.1 給定圖給定圖T,則以下關(guān)于樹(shù)的定義等價(jià)則以下關(guān)于樹(shù)的定義等價(jià): (1)T無(wú)回路且為連通圖無(wú)回路且為

57、連通圖; (2)T無(wú)回路且無(wú)回路且e e=v v-1,其中其中e e是邊數(shù)是邊數(shù),v v是結(jié)點(diǎn)數(shù)是結(jié)點(diǎn)數(shù); (3)T連通且連通且e e=v v-1; (4)T無(wú)回路無(wú)回路,但如果任意增加一條新的邊但如果任意增加一條新的邊,便得到便得到 一條且恰只得到一條回路一條且恰只得到一條回路; (5)T連通連通,但刪去任何一條邊后便不連通但刪去任何一條邊后便不連通; (6)T的每一對(duì)結(jié)點(diǎn)之間有唯一一條路的每一對(duì)結(jié)點(diǎn)之間有唯一一條路. 證明證明:(1)(2)(對(duì)結(jié)點(diǎn)數(shù)對(duì)結(jié)點(diǎn)數(shù)v v2用歸納法用歸納法.) 設(shè)設(shè)T無(wú)回路且為連通圖無(wú)回路且為連通圖,要證明要證明T無(wú)回路且無(wú)回路且e e=v v-1. 1)如果如果

58、v v=2,由于由于T無(wú)回路且連通無(wú)回路且連通,故必有故必有e e=1 e e=v v-1. 2)設(shè)結(jié)論對(duì)有設(shè)結(jié)論對(duì)有k k-1個(gè)結(jié)點(diǎn)的無(wú)回路連通圖已經(jīng)成立個(gè)結(jié)點(diǎn)的無(wú)回路連通圖已經(jīng)成立. 3)設(shè)圖設(shè)圖T有有v v=k k個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), ,它連通且無(wú)回路它連通且無(wú)回路.故它至少有一條故它至少有一條 邊邊e e1=(u,wu,w)的一個(gè)端點(diǎn)的一個(gè)端點(diǎn)u u度數(shù)為度數(shù)為1(否則圖否則圖T中就存在中就存在 一個(gè)結(jié)點(diǎn)度數(shù)均為偶數(shù)的子圖一個(gè)結(jié)點(diǎn)度數(shù)均為偶數(shù)的子圖T1, T1中必存在一條歐拉中必存在一條歐拉 回路回路,即圖即圖T中存在一條回路中存在一條回路,這是不可能的這是不可能的).從圖從圖T中去中去 掉

59、結(jié)點(diǎn)掉結(jié)點(diǎn)u u(邊邊e e1=(u,wu,w)也就同時(shí)被去掉也就同時(shí)被去掉,但但其它的邊不其它的邊不 受影響受影響),就得到一個(gè)有就得到一個(gè)有v v*=k k-1個(gè)結(jié)點(diǎn)的無(wú)回路的連通個(gè)結(jié)點(diǎn)的無(wú)回路的連通 圖圖T*.由歸納假設(shè)由歸納假設(shè),在圖在圖T*中有中有e e*=v v*-1=k k-2.最后再將結(jié)最后再將結(jié) 點(diǎn)點(diǎn)u u和它關(guān)聯(lián)的邊和它關(guān)聯(lián)的邊e e1=(u,wu,w)添加到圖添加到圖T*中去就得到圖中去就得到圖 T,于是在圖于是在圖T中有中有v v= v v*+1=k k和和e e=e e*+1=k k-1=v v-1,從而從而 結(jié)論對(duì)有結(jié)論對(duì)有k k個(gè)結(jié)點(diǎn)的樹(shù)依然成立個(gè)結(jié)點(diǎn)的樹(shù)依然成立

60、. w w u u 證明證明:(2)(3) 設(shè)設(shè)T無(wú)回路且無(wú)回路且e e=v v-1,要證明要證明T連通且連通且e e=v v-1. 用反證法用反證法.若若T不連通不連通,設(shè)它有設(shè)它有k k2個(gè)分支個(gè)分支 T1,T2,Tk k, 因?yàn)槊總€(gè)分支都是無(wú)回路的連通圖因?yàn)槊總€(gè)分支都是無(wú)回路的連通圖,若設(shè)若設(shè)Ti i有有v vi i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 和和e ei i條邊條邊,則由上證知?jiǎng)t由上證知e ei i=v vi i-1,從而對(duì)圖從而對(duì)圖T有有 e e= e e1+e e2+.+e ek k=(v v1-1)+(v v2-1)+(v vk k-1) =(v v1+v v2+v vk k)-k k=v v