離散數(shù)學(xué)第8章圖論

1、 主要內(nèi)容如下主要內(nèi)容如下 8.1 8.1 基本概念基本概念 8.6 8.6 有向樹(shù)有向樹(shù) 8.2 8.2 圖的矩陣表示圖的矩陣表示 8.7 8.7 二部圖二部圖 8.4 8.4 歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 8.8 8.8 平面圖平面圖 8.5 8.5 樹(shù)樹(shù) 8.9 8.9 有向圖有向圖第第 8 8 章章 圖論圖論 在第在第2 2章討論關(guān)系時(shí)，曾引進(jìn)過(guò)圖的一些概念。在那章討論關(guān)系時(shí)，曾引進(jìn)過(guò)圖的一些概念。在那里，圖只是作為表達(dá)集合上二元關(guān)系的一種工具。在這一里，圖只是作為表達(dá)集合上二元關(guān)系的一種工具。在這一章介紹圖的基本概念、基本性質(zhì)以及幾種在實(shí)際應(yīng)用中有章介紹圖的基本概念、基本性質(zhì)

2、以及幾種在實(shí)際應(yīng)用中有重要意義的特殊圖。鑒于學(xué)時(shí)有限，只介紹最基本的內(nèi)容。重要意義的特殊圖。鑒于學(xué)時(shí)有限，只介紹最基本的內(nèi)容。8.1 8.1 基本概念基本概念 一、圖的定義及其表示一、圖的定義及其表示（1 1） V=vV=v1 1，v v2 2，v vn n 是一個(gè)有限非空的集合，是一個(gè)有限非空的集合，V V中中的元素稱為的元素稱為G G的的結(jié)點(diǎn)（或頂點(diǎn)）結(jié)點(diǎn)（或頂點(diǎn)），V V稱為圖稱為圖G G的的結(jié)點(diǎn)集結(jié)點(diǎn)集，記，記作作 V V（G G）；）；（2 2）E E是是V V中中不同不同元素的元素的非有序非有序?qū)ε嫉募希瑢?duì)偶的集合，E E中的元素稱中的元素稱為為G G的的邊（或弧）邊（或弧），E

3、 E稱為圖稱為圖G G的的邊集邊集，記作，記作E E（G G）。）。一個(gè)圖一個(gè)圖 G G 是一個(gè)有序二元組（是一個(gè)有序二元組（V V，E E），其中：），其中：1. 1. 圖的定義圖的定義(1)(1) 圖解表示法圖解表示法(2)(2) 矩陣表示法：矩陣表示法：8.28.2節(jié)節(jié) 例例2 2 下圖下圖(a).(b)(a).(b)分別給出了例分別給出了例1 1中圖中圖G G的圖解表示。的圖解表示。 例例1 設(shè)設(shè) V =vV =v1 1，v v2 2，v v3 3，v v4 4，v v5 5, E = E = ,4342323121vvvvvvvvvvv,v,v,v54532. 2. 圖的表示方法圖的

4、表示方法則則 G=（V，E）是一個(gè)圖。是一個(gè)圖。 二二. 有關(guān)概念有關(guān)概念 1 1（n n，m m）圖）圖: : （n n，0 0）圖；）圖； （1，0）圖；）圖； 定義定義8-28-2 在圖在圖G G中，如果任意兩個(gè)不同的結(jié)點(diǎn)都是鄰中，如果任意兩個(gè)不同的結(jié)點(diǎn)都是鄰接的，則稱圖接的，則稱圖G G是是完全圖完全圖。n n個(gè)結(jié)點(diǎn)的完全圖記作個(gè)結(jié)點(diǎn)的完全圖記作 K Kn n例例3 3K1K2K3K4K52 2兩結(jié)點(diǎn)是兩結(jié)點(diǎn)是鄰接的；鄰接的；3 3邊和結(jié)點(diǎn)是邊和結(jié)點(diǎn)是關(guān)聯(lián)的；關(guān)聯(lián)的； 4 4孤立點(diǎn)；孤立點(diǎn)； 5 5兩條邊是兩條邊是鄰接的；鄰接的； 6 6孤立邊；孤立邊； 零圖零圖平凡圖平凡圖 定義定義

5、8-38-3 圖圖G G的的補(bǔ)圖補(bǔ)圖是由是由G G的所有結(jié)點(diǎn)和為了使的所有結(jié)點(diǎn)和為了使G G成為完全圖所需添加的那些邊組成的圖，用成為完全圖所需添加的那些邊組成的圖，用 表示。表示。G 例例4 4 下下圖中（圖中（b b）所表示的圖是（）所表示的圖是（a a）圖的補(bǔ)圖。）圖的補(bǔ)圖。注意：在注意：在 Kn 中，邊的數(shù)目為：中，邊的數(shù)目為：n(n-1)/2三、關(guān)于圖的基本術(shù)語(yǔ)三、關(guān)于圖的基本術(shù)語(yǔ)1、 偽圖：設(shè)圖偽圖：設(shè)圖G（V，E），），V是一個(gè)有限非空集合，是一個(gè)有限非空集合，E是是V中中任意元素任意元素的的非有序非有序?qū)ε嫉膶?duì)偶的多重集多重集，則稱，則稱G是一個(gè)是一個(gè)偽圖偽圖。多重集多重集：元

6、素可重復(fù)出現(xiàn)，且不要求：元素可重復(fù)出現(xiàn)，且不要求E中元素中元素v i, v j滿足滿足v i v j ,這這樣若樣若vi V，則有可能，則有可能v i, v i E，稱這樣的邊為，稱這樣的邊為自環(huán)自環(huán)。例：。例：V1V2V3V4V3V1V2V42、多重圖：沒(méi)有自環(huán)的偽圖稱為、多重圖：沒(méi)有自環(huán)的偽圖稱為多重圖多重圖。3、邊的重?cái)?shù)：連接于同一對(duì)結(jié)點(diǎn)間的邊的數(shù)目稱為邊的、邊的重?cái)?shù)：連接于同一對(duì)結(jié)點(diǎn)間的邊的數(shù)目稱為邊的重?cái)?shù)重?cái)?shù)。4、簡(jiǎn)單圖：沒(méi)有自環(huán)且沒(méi)有重?cái)?shù)大于、簡(jiǎn)單圖：沒(méi)有自環(huán)且沒(méi)有重?cái)?shù)大于1的邊的圖，稱為的邊的圖，稱為簡(jiǎn)單圖簡(jiǎn)單圖。 定義定義8-48-4：若圖若圖G的所有結(jié)點(diǎn)都具有相同的度數(shù)的所有

7、結(jié)點(diǎn)都具有相同的度數(shù)d，則稱，則稱圖圖G為為d d次正則圖次正則圖。例如：例如：GG是是3次正則圖次正則圖 四、四、結(jié)點(diǎn)的度和正則圖結(jié)點(diǎn)的度和正則圖 圖圖G中關(guān)聯(lián)結(jié)點(diǎn)中關(guān)聯(lián)結(jié)點(diǎn)vi 的邊的總數(shù)稱為結(jié)點(diǎn)的邊的總數(shù)稱為結(jié)點(diǎn)vi的的度度，用，用deg(vi ) 表示。表示。 握手定理握手定理 設(shè)圖設(shè)圖G G具有結(jié)點(diǎn)集具有結(jié)點(diǎn)集vv1 1，v v2 2，v vn n 和和m m條條邊，則邊，則G G中所有結(jié)點(diǎn)的度之和中所有結(jié)點(diǎn)的度之和 。n1iim2)vdeg(例如例如 右圖中所有結(jié)點(diǎn)的度之和右圖中所有結(jié)點(diǎn)的度之和51721423432)deg(iiv剛好是邊數(shù)剛好是邊數(shù)7 7的兩倍。的兩倍。 推論推

8、論 任何圖任何圖G G中，度為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。中，度為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。 證明證明 設(shè)圖設(shè)圖G G中，奇數(shù)度結(jié)點(diǎn)集為中，奇數(shù)度結(jié)點(diǎn)集為V V1 1，偶數(shù)度結(jié)點(diǎn)，偶數(shù)度結(jié)點(diǎn) 集為集為V V2 2，邊數(shù)為，邊數(shù)為m m， 則則 于是于是 m2)vdeg()vdeg()vdeg(21VvVvVv21VvVv)vdeg(m2)vdeg( 因?yàn)橐驗(yàn)?和和2m2m均為偶數(shù)，所以均為偶數(shù)，所以也必為偶數(shù)。由于當(dāng)也必為偶數(shù)。由于當(dāng)v v V V1 1時(shí)，時(shí)，deg(v)deg(v)均為奇數(shù)，均為奇數(shù)，因此因此#V#V1 1必為偶數(shù)。必為偶數(shù)。2Vvv)(deg1Vv)vdeg( 五、圖的同構(gòu)五、圖的

9、同構(gòu) 定義定義8-58-5 設(shè)設(shè)G G和和G G 是分別具有結(jié)點(diǎn)集是分別具有結(jié)點(diǎn)集V V和和V V 的兩個(gè)的兩個(gè)圖，若存在一個(gè)雙射圖，若存在一個(gè)雙射h h：V VV V ，使得當(dāng)且僅當(dāng)，使得當(dāng)且僅當(dāng) v vi i，v vj j 是是G G的邊時(shí)，的邊時(shí)，h(vh(vi i) )，h(vh(vj j)是是G G 的邊，則稱圖的邊，則稱圖G G與與G G 同同構(gòu)。構(gòu)。兩個(gè)圖同構(gòu)的必要條件是：兩個(gè)圖同構(gòu)的必要條件是：（1）它們有相同的結(jié)點(diǎn)數(shù)和相同的邊數(shù)；）它們有相同的結(jié)點(diǎn)數(shù)和相同的邊數(shù)；（2）對(duì)應(yīng)結(jié)點(diǎn)的度數(shù)相同。）對(duì)應(yīng)結(jié)點(diǎn)的度數(shù)相同。例例4 判斷下面的兩個(gè)圖是否同構(gòu)？判斷下面的兩個(gè)圖是否同構(gòu)？V3V

10、1V2V6V5V4U6U1U2U3U4U5 六、子圖六、子圖 利用子集的概念可定義圖利用子集的概念可定義圖G G的子圖。的子圖。 定義定義8-68-6 設(shè)有圖設(shè)有圖G G1 1= =（V V1 1，E E1 1）和圖）和圖G G2 2= =（V V2 2，E E2 2） （1 1） 若若V V2 2 V V1 1，E E2 2 E E1 1，則稱，則稱G G2 2是是G G1 1的的子圖子圖， 記作記作G G2 2 G G1 1；。 非真非真生成生成真真生成生成真真非生成非生成非真非真非生成非生成真真非生成非生成（2 2） 若若V V2 2 V V1 1，E E2 2 E E1 1，則稱，則稱

11、G G2 2是是G G1 1的的真子圖真子圖； （3 3） 若若V V2 2 = V = V1 1，E E2 2 E E1 1，則稱，則稱G G2 2是是G G1 1的的生成子圖生成子圖. .七、路與回路七、路與回路 定義定義: :圖圖G G中中l(wèi)條邊的序列條邊的序列vv0 0，v v1 1vv1 1，v v2 2 vvl1 1，v vl 稱為連稱為連接接v v0 0到到v vl的一條長(zhǎng)為的一條長(zhǎng)為 l 的的路路。它常簡(jiǎn)單地用結(jié)點(diǎn)的序列。它常簡(jiǎn)單地用結(jié)點(diǎn)的序列v v0 0v v1 1v v2 2v vl1 1v vl來(lái)表示。其中來(lái)表示。其中v v0 0和和v vl分別稱為這條路的起點(diǎn)和終點(diǎn)。分

12、別稱為這條路的起點(diǎn)和終點(diǎn)。開(kāi)路開(kāi)路：若：若v v0 0 v vl，則稱路，則稱路v v0 0v v1 1v v2 2v vl1 1v vl為為開(kāi)路開(kāi)路；回路回路：若：若v v0 0=v=vl，則稱路，則稱路v v0 0v v1 1v v2 2v vl1 1v vl為為回路回路；環(huán)環(huán)：在：在回路回路v v0 0v v1 1v v2 2v vl1 1v v0 0中，若中，若v v0 0，v v1 1，v v2 2，v vl1 1 各不相同各不相同（此時(shí)所有邊也互不相同），則稱該回路為（此時(shí)所有邊也互不相同），則稱該回路為環(huán)環(huán)。真路真路：若：若開(kāi)路開(kāi)路v v0 0v v1 1v v2 2v vl1

13、1v vl中，所有結(jié)點(diǎn)互不相同（此時(shí)所有中，所有結(jié)點(diǎn)互不相同（此時(shí)所有邊也互不相同），則稱該路為邊也互不相同），則稱該路為真路真路；例例在圖在圖G中，若存在一條路連接中，若存在一條路連接vi和和vj，則稱結(jié)點(diǎn)，則稱結(jié)點(diǎn)vi與與vj是是連連接的接的. 例例 上例給出的圖是連通圖，下圖給出的是非連通圖。上例給出的圖是連通圖，下圖給出的是非連通圖。八、連通圖和分圖八、連通圖和分圖 定義定義8-78-7 在圖在圖G G中，若任意兩個(gè)結(jié)點(diǎn)都是中，若任意兩個(gè)結(jié)點(diǎn)都是連接連接的，則的，則稱稱G G是是連通圖連通圖，否則，稱，否則，稱G G為為非連通圖非連通圖。僅有一個(gè)孤立結(jié)。僅有一個(gè)孤立結(jié)點(diǎn)的圖定義它為連通

14、圖。點(diǎn)的圖定義它為連通圖。 定義定義 設(shè)設(shè)H H是圖是圖G G的子圖，若的子圖，若H H滿足以下兩個(gè)條件：滿足以下兩個(gè)條件： （1 1）H H是連通的；是連通的； （2 2）對(duì)）對(duì)G G的任意子圖的任意子圖H H ，若，若H H H H，且，且H H H H G G，則，則H H 不是連通的。不是連通的。注注: （2）的言外之意是：）的言外之意是：H H是是G G的最大連通子圖。的最大連通子圖。則稱則稱H H是是G G的的分圖分圖。例例 解解 （b b）顯然不是）顯然不是G G的分圖，因?yàn)椋ǖ姆謭D，因?yàn)椋╞ b）不連通；）不連通； （c）也不是）也不是G的分圖；的分圖； （d）是）是G的分圖；

15、的分圖；（e）是）是G的分圖。的分圖。 2 2割邊割邊：如果在圖：如果在圖G G中刪去邊中刪去邊 v vi i，v vj j 后，圖后，圖G G的分的分圖數(shù)增加，則稱邊圖數(shù)增加，則稱邊 v vi i，v vj j 是是G G的的割邊割邊。邊邊vv4 4，v v5 5 和和 v v4 4，v v6 6 均是割邊。均是割邊。 1 1割點(diǎn)割點(diǎn)：如果在圖：如果在圖G G中刪去結(jié)點(diǎn)中刪去結(jié)點(diǎn)v v（及與其相關(guān)聯(lián)的所（及與其相關(guān)聯(lián)的所有邊后），圖有邊后），圖G G的分圖數(shù)增加，則稱結(jié)點(diǎn)的分圖數(shù)增加，則稱結(jié)點(diǎn)v v是是G G的的割點(diǎn)割點(diǎn)。 例例1010 下圖中圖中v4 ，v6均是割點(diǎn)；均是割點(diǎn)； 結(jié)論：在圖

16、結(jié)論：在圖G G中，邊中，邊vvi i，v vj j 為割邊當(dāng)且僅當(dāng)邊邊v vi i，v vj j 不不在在G G的任何環(huán)中出現(xiàn)。的任何環(huán)中出現(xiàn)。證明：設(shè)證明：設(shè)e是是G（V，E）的任意一條邊，）的任意一條邊，ev i, v j設(shè)設(shè)e是割邊，用反證法是割邊，用反證法假設(shè)假設(shè)e包含在包含在G的某一環(huán)路的某一環(huán)路C中，則中，則C= l v i, v j，其中，其中l(wèi)是是一條不含一條不含e的連接的連接vi，v j 的真路。的真路。所以刪去所以刪去e后，得后，得G=G-e，G仍然聯(lián)通，這與仍然聯(lián)通，這與e是割邊矛盾。是割邊矛盾。因此，因此，e不包含在不包含在G的任一環(huán)路中。的任一環(huán)路中。設(shè)設(shè)e不包含在

17、不包含在G的任何環(huán)路中。用反證法的任何環(huán)路中。用反證法假設(shè)假設(shè)e不是割邊，則在不是割邊，則在G中刪去邊中刪去邊e=v i, v j后后得圖得圖G，G 是聯(lián)通的，所以在是聯(lián)通的，所以在G 中有一條連中有一條連接接vi，v j的路。的路。由定理由定理8-2知，可得到一條連接知，可得到一條連接vi，v j的真路的真路 l ，則，則G中中 l v I ,v j是是G中的一個(gè)環(huán)路，這與條件矛盾。中的一個(gè)環(huán)路，這與條件矛盾。因此，假設(shè)錯(cuò)誤，因此，假設(shè)錯(cuò)誤，e是割邊。是割邊。 2 2距離距離：結(jié)點(diǎn)：結(jié)點(diǎn)v vi i和和v vj j間的短程的長(zhǎng)度稱為間的短程的長(zhǎng)度稱為v vi i和和v vj j間的間的距離距

18、離，用，用d d（v vi i，v vj j）表示。）表示。九、短程和距離九、短程和距離 1 1短程短程：在圖：在圖G G中，結(jié)點(diǎn)中，結(jié)點(diǎn)v vi i和和v vj j若由一條或更多條若由一條或更多條路相連接，則其中必有長(zhǎng)度最短的路，稱它為從路相連接，則其中必有長(zhǎng)度最短的路，稱它為從v vi i到到v vj j的的短程短程。3),(1),(2),(612151vvdvvdvvd例例證明證明 設(shè)設(shè) 為任一連接為任一連接v vi i到到v vj j的路，且的路，且 = v= vi iu u1 1 u u2 2u ur ru uk ku ul1 1v vj j，若若 中有相同的結(jié)點(diǎn)，設(shè)為中有相同的結(jié)點(diǎn)

19、，設(shè)為u ur r= u= uk k（rkr2nS2n2 2，也與，也與S=2nS=2n2 2矛盾。矛盾。由上可知，由上可知，T T中至少有兩片樹(shù)葉。中至少有兩片樹(shù)葉。 樹(shù)的有些性質(zhì)可用來(lái)作為樹(shù)的定義，我們列出下面樹(shù)的有些性質(zhì)可用來(lái)作為樹(shù)的定義，我們列出下面四條四條：（1 1）每?jī)蓚€(gè)結(jié)點(diǎn)間由唯一的真路相連接的圖是樹(shù)；）每?jī)蓚€(gè)結(jié)點(diǎn)間由唯一的真路相連接的圖是樹(shù)；（2 2）m=nm=n1 1的連通圖是樹(shù)；的連通圖是樹(shù)； (3(3）m=nm=n1 1且無(wú)環(huán)的圖是樹(shù)；且無(wú)環(huán)的圖是樹(shù)； (4) (4) 每條邊為割邊的連通圖是樹(shù)。每條邊為割邊的連通圖是樹(shù)。（樹(shù)的等價(jià)定義樹(shù)的等價(jià)定義）8.5 8.5 樹(shù)樹(shù)一、

20、樹(shù)的定義一、樹(shù)的定義二、樹(shù)的性質(zhì)二、樹(shù)的性質(zhì)三、生成樹(shù)與最小生成樹(shù)三、生成樹(shù)與最小生成樹(shù) 三、生成樹(shù)與最小生成樹(shù)三、生成樹(shù)與最小生成樹(shù) 1 1生成樹(shù)生成樹(shù) 定義定義 若連通圖若連通圖G G的生成子圖的生成子圖T T是一棵樹(shù)，則稱是一棵樹(shù)，則稱T T為為G G的的生成樹(shù)生成樹(shù)。 例例2 2 下下圖中（圖中（b b）和（）和（c c）都是（）都是（a a）的生成樹(shù)。）的生成樹(shù)。 2 2構(gòu)造連通圖構(gòu)造連通圖G=G=（V V，E E）的生成樹(shù)的方法）的生成樹(shù)的方法 （a a）破環(huán)法）破環(huán)法 例例3 3 用破環(huán)法，構(gòu)造上頁(yè)圖（用破環(huán)法，構(gòu)造上頁(yè)圖（a a）的生成樹(shù)的過(guò)程如下：）的生成樹(shù)的過(guò)程如下： （b

21、 b）避環(huán)法）避環(huán)法例例4 4 用避環(huán)法構(gòu)造（用避環(huán)法構(gòu)造（a a）的生成樹(shù)過(guò)程如下：）的生成樹(shù)過(guò)程如下： 3 3最小生成樹(shù)最小生成樹(shù) 定義定義8-158-15 每條邊都指定了權(quán)的圖稱為每條邊都指定了權(quán)的圖稱為有權(quán)圖有權(quán)圖。當(dāng)當(dāng)G G是一有權(quán)圖時(shí)，常將其表示為有序三元組是一有權(quán)圖時(shí)，常將其表示為有序三元組G=G=（V V，E E，f f），），這里這里f f是一由邊集是一由邊集E E到實(shí)數(shù)集到實(shí)數(shù)集R R的函數(shù)的函數(shù) f f：E ER.R. 例例5 下圖是一連通有權(quán)圖。下圖是一連通有權(quán)圖。 v 定義定義 設(shè)設(shè)G=G=（V V，E E，f f）是一連通有權(quán)圖，）是一連通有權(quán)圖，T T是是G G的

22、一棵生成樹(shù)，的一棵生成樹(shù)，T T的邊集用的邊集用E E（T T）表示，）表示，T T的各邊權(quán)值之的各邊權(quán)值之和和W W（T T）= 稱為稱為T(mén) T的權(quán)。的權(quán)。G G的所有生成樹(shù)中權(quán)的所有生成樹(shù)中權(quán)最小的生成樹(shù)稱為最小的生成樹(shù)稱為G G的的最小生成樹(shù)最小生成樹(shù)。)T(Ee)e(f 例例6 6 它們的權(quán)它們的權(quán)W W（T T1）=24，W W（T T2）=30。 4 4構(gòu)造連通有權(quán)圖的最小生成樹(shù)的方法構(gòu)造連通有權(quán)圖的最小生成樹(shù)的方法 例例7 7 以例以例5中圖為例，中圖為例， （1 1） 破環(huán)法破環(huán)法 G=G1G2G3G4G5G6=T0W(T0)=18 （2 2） 避環(huán)法避環(huán)法G=G1G1G2G3

23、G4G5 = T0練習(xí)練習(xí)8-58-5 1 1設(shè)樹(shù)設(shè)樹(shù)T T有有7 7條邊，問(wèn)條邊，問(wèn)T T有多少個(gè)結(jié)點(diǎn)？（有多少個(gè)結(jié)點(diǎn)？（ ） 2 2設(shè)設(shè)G G是一個(gè)樹(shù)林，由是一個(gè)樹(shù)林，由3 3個(gè)分圖組成，若個(gè)分圖組成，若G G有有1515個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，問(wèn)問(wèn)G G有多少條邊？（有多少條邊？（ ） 3 3互不同構(gòu)的互不同構(gòu)的2 2結(jié)點(diǎn)樹(shù)有（結(jié)點(diǎn)樹(shù)有（ ）棵？）棵？ 互不同構(gòu)的互不同構(gòu)的4 4結(jié)點(diǎn)樹(shù)有（結(jié)點(diǎn)樹(shù)有（ ）棵？）棵？8 812121 12 22424 4求下圖給出的有權(quán)圖的最小生成樹(shù)的權(quán)（求下圖給出的有權(quán)圖的最小生成樹(shù)的權(quán)（ ） 8.6 8.6 有向樹(shù)有向樹(shù)一、有向圖一、有向圖 若在圖若在圖 G=（

24、V，E）中，V是一有限非空集合，E是V中不同元素的有序?qū)ε嫉募希瑒t稱G是一有向圖。有向圖中的概念（2） 始點(diǎn)，終點(diǎn)；（3） 出度，入度，度。（1）有向路：有向開(kāi)路，有向回路，有向真路，有向環(huán)；二、有向樹(shù)的定義二、有向樹(shù)的定義 定義定義8-228-22 一個(gè)不包含環(huán)的有向圖一個(gè)不包含環(huán)的有向圖G G，若它只，若它只有一個(gè)結(jié)點(diǎn)有一個(gè)結(jié)點(diǎn)v v0 0的的入度入度為為0 0，而其它所有結(jié)點(diǎn)的，而其它所有結(jié)點(diǎn)的入度入度都等都等于于1 1，則稱，則稱G G是是有向樹(shù)有向樹(shù)，v v0 0稱為樹(shù)的稱為樹(shù)的根根。 例例1 1 下下圖給出的圖是否有向樹(shù)？圖給出的圖是否有向樹(shù)？一個(gè)孤立的結(jié)點(diǎn)也是一棵有向樹(shù)。一個(gè)孤

25、立的結(jié)點(diǎn)也是一棵有向樹(shù)。 有向樹(shù)中的一些概念有向樹(shù)中的一些概念 （1 1） 樹(shù)葉；樹(shù)葉； （2 2） 分枝結(jié)點(diǎn)；分枝結(jié)點(diǎn)； （3 3） 級(jí)，樹(shù)高；級(jí)，樹(shù)高；一級(jí)結(jié)點(diǎn)二級(jí)結(jié)點(diǎn)三級(jí)結(jié)點(diǎn)（4 4）兒子、父親、兄弟、祖先和子孫（后代）；）兒子、父親、兄弟、祖先和子孫（后代）； 有向樹(shù)的圖解有向樹(shù)的圖解( (箭頭可省箭頭可省) )表示表示有向樹(shù)有向樹(shù)：一個(gè)結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)v v0 0的的入度入度為為0 0，其它所有結(jié)點(diǎn)的，其它所有結(jié)點(diǎn)的入度入度都都等于等于1 1（4 4）以以u(píng) u為根的子樹(shù)：為根的子樹(shù)：設(shè)設(shè)u u是有向樹(shù)是有向樹(shù)T T的分枝結(jié)點(diǎn)，由結(jié)點(diǎn)的分枝結(jié)點(diǎn)，由結(jié)點(diǎn)u u和它的所有子孫構(gòu)成的結(jié)點(diǎn)集和

26、它的所有子孫構(gòu)成的結(jié)點(diǎn)集U U ，以及從，以及從u u出發(fā)的所有有向出發(fā)的所有有向路中的邊構(gòu)成的邊集路中的邊構(gòu)成的邊集E E 組成組成T T的子圖的子圖T T = =（U U ，E E ）稱為是以）稱為是以u(píng) u為根的為根的T T的子樹(shù)；的子樹(shù)；有向樹(shù)中的一些概念有向樹(shù)中的一些概念一級(jí)結(jié)點(diǎn)二級(jí)結(jié)點(diǎn)三級(jí)結(jié)點(diǎn)（5 5）u u的子樹(shù)：的子樹(shù)：以以u(píng) u的兒子為根的子樹(shù)。的兒子為根的子樹(shù)。 T T1 1又稱為是又稱為是v v0 0的子樹(shù)。的子樹(shù)。v v0 0的另一棵子樹(shù)是以的另一棵子樹(shù)是以v v2 2為根為根的子樹(shù)。的子樹(shù)。 子圖子圖T T1 1= =（V V1 1，E E1 1）是以）是以v v1

27、1為根的子樹(shù)。其中為根的子樹(shù)。其中 V V1 1 = =v v1 1，v v3 3，v v4 4，v v5 5, , E E1 1 = =（v v1 1,v v3 3）, ,（v v1 1,v v4 4），（v v1 1，v v5 5）。例例2 2T T1 1=（V V1 1，E E1 1）三、二元樹(shù)三、二元樹(shù) 定義定義8-238-23 在一有向樹(shù)中，若每一結(jié)點(diǎn)的出度在一有向樹(shù)中，若每一結(jié)點(diǎn)的出度都小于或等于都小于或等于m m，則稱這棵樹(shù)為，則稱這棵樹(shù)為m m元樹(shù)元樹(shù)；若每一個(gè)結(jié)點(diǎn)；若每一個(gè)結(jié)點(diǎn)的出度恰好等于的出度恰好等于m m或或0，則稱這棵樹(shù)為，則稱這棵樹(shù)為完全完全m m元樹(shù)元樹(shù)。 例例3

28、 3 二元樹(shù)二元樹(shù)完全二元樹(shù)完全二元樹(shù)滿滿二元樹(shù)二元樹(shù)三元樹(shù)三元樹(shù) 當(dāng)當(dāng)m=2m=2時(shí)，分別稱其為時(shí)，分別稱其為二元樹(shù)二元樹(shù)和和完全二元樹(shù)完全二元樹(shù)。若二。若二元樹(shù)的所有樹(shù)葉結(jié)點(diǎn)在同一級(jí)別則稱它為元樹(shù)的所有樹(shù)葉結(jié)點(diǎn)在同一級(jí)別則稱它為滿二元樹(shù)滿二元樹(shù)。1 1先根通過(guò)先根通過(guò) （1 1）訪問(wèn)根；）訪問(wèn)根； (2(2）在根的左子樹(shù)上執(zhí)行先根通過(guò)；）在根的左子樹(shù)上執(zhí)行先根通過(guò)； （3 3）在根的右子樹(shù)上執(zhí)行先根）在根的右子樹(shù)上執(zhí)行先根通過(guò)通過(guò)。 四、訪問(wèn)二元樹(shù)四、訪問(wèn)二元樹(shù) 下面介紹訪問(wèn)二元樹(shù)常用的三種方法：下面介紹訪問(wèn)二元樹(shù)常用的三種方法：先根訪問(wèn)結(jié)果為先根訪問(wèn)結(jié)果為_(kāi)。a a b b c c d

29、df fg gi ie eh h例例 2 2中根通過(guò)中根通過(guò) （1 1）在根的左子樹(shù)上執(zhí)行中根）在根的左子樹(shù)上執(zhí)行中根通過(guò)通過(guò)； （2 2）訪問(wèn)根；）訪問(wèn)根； （3 3）在根的右子樹(shù)上執(zhí)行中根）在根的右子樹(shù)上執(zhí)行中根通過(guò)通過(guò)。 四、訪問(wèn)二元樹(shù)四、訪問(wèn)二元樹(shù) 下面介紹訪問(wèn)二元樹(shù)常用的三種方法：下面介紹訪問(wèn)二元樹(shù)常用的三種方法：d db bc c e ea af fi ig gh h中根訪問(wèn)結(jié)果為中根訪問(wèn)結(jié)果為_(kāi)。例例 3 3后根通過(guò)后根通過(guò) （1 1）在根的左子樹(shù)上執(zhí)行后根）在根的左子樹(shù)上執(zhí)行后根通過(guò)通過(guò)； （2 2）在根的右子樹(shù)上執(zhí)行后根）在根的右子樹(shù)上執(zhí)行后根通過(guò)通過(guò)； （3 3）訪問(wèn)根。）

30、訪問(wèn)根。 四、訪問(wèn)二元樹(shù)四、訪問(wèn)二元樹(shù) 下面介紹訪問(wèn)二元樹(shù)常用的三種方法：下面介紹訪問(wèn)二元樹(shù)常用的三種方法：d df fc ch h i ie eg gb ba a后根訪問(wèn)結(jié)果為后根訪問(wèn)結(jié)果為_(kāi)。例例 定義定義8-248-24 在有向樹(shù)中，在有向樹(shù)中，若規(guī)定了每一級(jí)上結(jié)點(diǎn)的次序，則若規(guī)定了每一級(jí)上結(jié)點(diǎn)的次序，則稱這樣的有向樹(shù)為稱這樣的有向樹(shù)為有序樹(shù)有序樹(shù)。 例例4 4 用二元有序樹(shù)表示算術(shù)表達(dá)式用二元有序樹(shù)表示算術(shù)表達(dá)式 和和 。)fe (dcbaa)fe(dcb例如例如 右圖（右圖（a a）和（）和（b b）表示）表示兩棵不同的有序樹(shù)。兩棵不同的有序樹(shù)。解解 例例5 5 （1 1）用二元有序

31、樹(shù)表示算術(shù)表達(dá)式）用二元有序樹(shù)表示算術(shù)表達(dá)式 )hg (f) ed (c) ba ( （2 2）用三種方法訪問(wèn)此樹(shù)，寫(xiě)出訪問(wèn)結(jié)果。）用三種方法訪問(wèn)此樹(shù)，寫(xiě)出訪問(wèn)結(jié)果。 )gh( f)de(c )ab(先根訪問(wèn)先根訪問(wèn) )hg (f) ed (c)ba (中根訪問(wèn)中根訪問(wèn))gh(f)de(c )ab(后根訪問(wèn)后根訪問(wèn)五、有向樹(shù)中的一些數(shù)量關(guān)系五、有向樹(shù)中的一些數(shù)量關(guān)系有向樹(shù)和無(wú)向樹(shù)一樣，滿足關(guān)系式有向樹(shù)和無(wú)向樹(shù)一樣，滿足關(guān)系式 m = nm = n1 1 定理定理8-208-20 設(shè)設(shè)T T是一棵完全是一棵完全m m元樹(shù)，樹(shù)葉結(jié)點(diǎn)數(shù)為元樹(shù)，樹(shù)葉結(jié)點(diǎn)數(shù)為n n0 0，分枝結(jié)點(diǎn)數(shù)為分枝結(jié)點(diǎn)數(shù)為t t

32、，則（，則（m m1 1）t=nt=n0 01 1。結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為 n n0 0+t+t， 于是于是mt=nmt=n0 0+t+t1 1證明證明 由完全由完全m m元樹(shù)的定義知，元樹(shù)的定義知，T T的邊數(shù)的邊數(shù)=mt=mt，即即 （m m1 1）t=nt=n0 01 1 定理定理8-188-18 設(shè)設(shè)T T是一棵二元樹(shù)，是一棵二元樹(shù)，n n0 0 表示樹(shù)葉結(jié)點(diǎn)數(shù)，表示樹(shù)葉結(jié)點(diǎn)數(shù)，n n2 2表示出度為表示出度為2 2的結(jié)點(diǎn)數(shù)，則的結(jié)點(diǎn)數(shù)，則n n2 2 = n= n0 0-1-1。 證明證明 設(shè)設(shè)T T的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n n ，出度為，出度為1 1的的 結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n n1 1，邊數(shù)

33、為，邊數(shù)為m m ， 則則 n = nn = n0 0+n+n1 1+n+n2 2 m = nm = n1 1+2n+2n2 2于是于是 n n1 1+2n+2n2 2 = n= n0 0+n+n1 1+n+n2 21 1 因此因此 n n2 2 = n n0 01 。m = nm = n1 1又又 定理定理8-198-19 設(shè)設(shè)T T是一棵完全二元樹(shù)，有是一棵完全二元樹(shù)，有n n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，n n0 0個(gè)個(gè)樹(shù)葉結(jié)點(diǎn)，則樹(shù)葉結(jié)點(diǎn)，則 n n = 2n= 2n0-1-1。 證明證明 設(shè)設(shè)T T有有n n2 2個(gè)出度為個(gè)出度為2 2的結(jié)點(diǎn)，則的結(jié)點(diǎn)，則n = nn = n0+n+n2 n =

34、nn = n0+ +（n n0 -1-1）即即 n = 2n0- -1。n n2 = n n01推論推論 完全二元樹(shù)有奇數(shù)個(gè)結(jié)點(diǎn)。完全二元樹(shù)有奇數(shù)個(gè)結(jié)點(diǎn)。 由定理由定理 8-188-18因此因此練習(xí)練習(xí) 8-68-6填空：填空： （1）2個(gè)結(jié)點(diǎn)非同構(gòu)的有向樹(shù)的個(gè)數(shù)是個(gè)結(jié)點(diǎn)非同構(gòu)的有向樹(shù)的個(gè)數(shù)是 。 （2）3個(gè)結(jié)點(diǎn)非同構(gòu)的有向樹(shù)的個(gè)數(shù)是個(gè)結(jié)點(diǎn)非同構(gòu)的有向樹(shù)的個(gè)數(shù)是 。 （3）4個(gè)結(jié)點(diǎn)非同構(gòu)的有向樹(shù)的個(gè)數(shù)是個(gè)結(jié)點(diǎn)非同構(gòu)的有向樹(shù)的個(gè)數(shù)是 。1 14 42 28.7 8.7 二部圖二部圖 二、匹配二、匹配一、二部圖一、二部圖 若若V V1 1中任一結(jié)點(diǎn)與中任一結(jié)點(diǎn)與V V2 2中每一結(jié)點(diǎn)均有邊相連接，

35、則稱二部中每一結(jié)點(diǎn)均有邊相連接，則稱二部圖為圖為完全二部圖完全二部圖。若。若#V#V1 1=r=r，#V#V2 2=t=t，則記完全二部圖，則記完全二部圖G G為為K Kr, tr, t。定義定義8-268-26 二部圖二部圖: : G=G=（V V1 1，V V2 2，E E）, , V V1 1和和V V2 2稱為稱為G G的互補(bǔ)結(jié)點(diǎn)子集。的互補(bǔ)結(jié)點(diǎn)子集。一、二部圖一、二部圖例例V V4 4V V1 1V V2 2例例1 1 如下所示的圖是否二部圖？如下所示的圖是否二部圖？二部圖不一定是連通圖。二部圖不一定是連通圖。定理定理8-238-23 圖圖G G為二部圖的充要條件是為二部圖的充要條件

36、是G G的所有回的所有回路均為偶數(shù)長(zhǎng)。路均為偶數(shù)長(zhǎng)。 二、匹配二、匹配 例例2 2 下圖所給出的二部圖是否存在圖所給出的二部圖是否存在V V1 1對(duì)對(duì)V V2 2的匹配？的匹配？是否存在是否存在V V2 2對(duì)對(duì)V V1 1的匹配？的匹配？ 定義定義8-27 8-27 設(shè)設(shè)G G是具有互補(bǔ)結(jié)點(diǎn)子集是具有互補(bǔ)結(jié)點(diǎn)子集V V1 1和和V V2 2的二部圖，的二部圖，其中其中V V1 1=v=v1 1，v v2 2，v vr r ，V V1 1對(duì)對(duì)V V2 2的匹配是的匹配是G G的一個(gè)子圖，的一個(gè)子圖，它由它由r r條邊條邊vv1 1，v v 1 1 ，vv2 2，v v 2 2 ，vvr r，v

37、v r r 組成，其中，組成，其中，v v 1 1，v v 2 2，v v r r是是V V2 2中中r r個(gè)不同的元素個(gè)不同的元素。 例例3 3 某班級(jí)成立了三個(gè)運(yùn)動(dòng)隊(duì)：籃球隊(duì)、排球隊(duì)某班級(jí)成立了三個(gè)運(yùn)動(dòng)隊(duì)：籃球隊(duì)、排球隊(duì)和足球隊(duì)。今有張、王、李、趙、陳和足球隊(duì)。今有張、王、李、趙、陳5 5名同學(xué)，若已知張、名同學(xué)，若已知張、王為籃球隊(duì)員；張、李、趙為排球隊(duì)員；李、趙、陳為足王為籃球隊(duì)員；張、李、趙為排球隊(duì)員；李、趙、陳為足球隊(duì)員，問(wèn)能否從這球隊(duì)員，問(wèn)能否從這5 5人中選出人中選出3 3名不兼職的隊(duì)長(zhǎng)？名不兼職的隊(duì)長(zhǎng)？在圖中存在在圖中存在V V1 1對(duì)對(duì)V V2 2的匹配，因此題目的要求可以

38、滿足。的匹配，因此題目的要求可以滿足。 解解構(gòu)造二部圖構(gòu)造二部圖 G=G=（V V1 1，V V2 2，E E）如下：）如下： V V1 1V V2 2定理8-24 設(shè)設(shè)G（V1，V2，E）是一個(gè)二部圖，則）是一個(gè)二部圖，則G中存在一中存在一個(gè)個(gè)V1對(duì)對(duì)V2的匹配的充要條件是，的匹配的充要條件是，V1中每中每k個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k=1,2,.,#V1)至少和至少和V2中的中的k個(gè)結(jié)點(diǎn)相鄰接。（該條件為相異性條件）個(gè)結(jié)點(diǎn)相鄰接。（該條件為相異性條件）定理8-25 設(shè)設(shè)G是一具有互補(bǔ)結(jié)點(diǎn)子集是一具有互補(bǔ)結(jié)點(diǎn)子集V1和和V2的二部圖，則的二部圖，則G具具有有V1對(duì)對(duì)V2的匹配的充分條件是：存在某一整數(shù)

39、的匹配的充分條件是：存在某一整數(shù)t0，使：，使：（1）對(duì)）對(duì)V1中的每個(gè)結(jié)點(diǎn)，至少有中的每個(gè)結(jié)點(diǎn)，至少有t條邊與其相關(guān)聯(lián)；條邊與其相關(guān)聯(lián)；（2）對(duì)）對(duì)V2中的每個(gè)結(jié)點(diǎn)，至多有中的每個(gè)結(jié)點(diǎn)，至多有t條邊與其相關(guān)聯(lián)。條邊與其相關(guān)聯(lián)。v1v3v2v4v8v5v6v7v9v10v11v12V1V2例例它的互補(bǔ)結(jié)點(diǎn)子集是：它的互補(bǔ)結(jié)點(diǎn)子集是： V V1 1= = V V2 2= = 練習(xí)練習(xí)8-78-7 1 1（1 1）圖）圖(a)(a)是否為二部圖？（是否為二部圖？（ ） v v1 1，v v3 3，v v5 5，v v6 6v v2 2，v v4 4，v v7 7Y(a)(a) 1 1（2 2）圖）

40、圖(b)(b)是否為二部圖？（是否為二部圖？（ ） N N(b)(b)8.8 8.8 平面圖平面圖二、平面圖的判定二、平面圖的判定一、平面圖的定義一、平面圖的定義一、平面圖的定義一、平面圖的定義例例1 1定義定義8-288-28 一個(gè)圖一個(gè)圖G G若能畫(huà)在平面上而邊無(wú)任何交叉，若能畫(huà)在平面上而邊無(wú)任何交叉，則稱則稱G G為為平面圖平面圖, ,否則稱圖否則稱圖G G為非平面圖為非平面圖。畫(huà)出的沒(méi)有邊交。畫(huà)出的沒(méi)有邊交叉的圖解稱為叉的圖解稱為G G的一個(gè)的一個(gè)平面嵌入平面嵌入。 設(shè)設(shè)G G是畫(huà)于平面上的一個(gè)圖，是畫(huà)于平面上的一個(gè)圖， =v=v1 1 v v2 2 v v3 3 v v4 4 v v

41、1 1是是G G中任意一個(gè)環(huán)。中任意一個(gè)環(huán)。 = v= v1 1v v3 3和和=v=v2 2v v4 4是是G G中任意兩中任意兩條邊無(wú)公共結(jié)點(diǎn)的真路。條邊無(wú)公共結(jié)點(diǎn)的真路。二、平面圖的判定二、平面圖的判定1 1簡(jiǎn)單、直觀判定法簡(jiǎn)單、直觀判定法 例例2 2 用上述簡(jiǎn)單、直觀的方法判斷下圖中的兩用上述簡(jiǎn)單、直觀的方法判斷下圖中的兩圖是否平面圖。圖是否平面圖。 2. 2. 歐拉公式判斷法歐拉公式判斷法 例例3 3 概念概念 (1) (1) 面面，邊界邊界； (2) (2) 有限面有限面，無(wú)限面無(wú)限面； 注意：注意：對(duì)于每一個(gè)平面圖，恰有一個(gè)無(wú)限面。對(duì)于每一個(gè)平面圖，恰有一個(gè)無(wú)限面。 (3) (3

42、) 面是相鄰的面是相鄰的，面是不相鄰的面是不相鄰的。 定理定理8-268-26 設(shè)設(shè)G G是一連通平面圖，有是一連通平面圖，有n n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，m m條邊，條邊，k k個(gè)面，則個(gè)面，則 n nm+k=2m+k=2此定理中的公式稱為歐拉公式。此定理中的公式稱為歐拉公式。 證明證明 （對(duì)邊數(shù)（對(duì)邊數(shù)m m進(jìn)行歸納）進(jìn)行歸納） 當(dāng)當(dāng)m=0m=0和和m=1m=1時(shí)，定理顯然成立。時(shí)，定理顯然成立。 假設(shè)定理對(duì)假設(shè)定理對(duì)m m1 1條邊的任何連通平面圖均成立，設(shè)條邊的任何連通平面圖均成立，設(shè)G G是一是一具有具有n n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，m m條邊，條邊，k k個(gè)面的連通平面圖（個(gè)面的連通平面圖（m2m

43、2） 由歸納假設(shè)由歸納假設(shè)G G 中歐拉公式成立。中歐拉公式成立。 因此因此n n（m m1 1）+ +（k k1 1）=2=2，即，即n nm+k=2m+k=2。 若若G G中沒(méi)有環(huán)，則中沒(méi)有環(huán)，則G G是一棵樹(shù)，是一棵樹(shù)，k=1k=1，且，且m m=n-1n-1，于是，于是n nm m+k k=n n-(n n-1 1) +1=21=2。 若若G G中有環(huán)，則去掉中有環(huán)，則去掉G G的任一環(huán)上的一條邊的任一環(huán)上的一條邊e e，剩下的圖，剩下的圖G G 仍連通，有仍連通，有n n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，k k1 1個(gè)面，個(gè)面，m m1 1條邊，條邊， 定理定理8-278-27 設(shè)設(shè)G G是一（是一（

44、n n，m m）的連通平面圖，）的連通平面圖，m2m2，則，則 m3nm3n6 . 6 . 證明證明 當(dāng)當(dāng) m=2 m=2 時(shí)，因時(shí)，因G G是簡(jiǎn)單圖必?zé)o環(huán)，所以是簡(jiǎn)單圖必?zé)o環(huán)，所以n=3n=3，上式成，上式成立。立。 當(dāng)當(dāng) m2 m2 時(shí)，每個(gè)面至少由三條邊圍成，因此各面時(shí)，每個(gè)面至少由三條邊圍成，因此各面邊界的邊數(shù)之和邊界的邊數(shù)之和3k3k； 另一方面，因?yàn)橐粭l邊最多在兩個(gè)面的邊界中，另一方面，因?yàn)橐粭l邊最多在兩個(gè)面的邊界中，在在中作了重復(fù)計(jì)數(shù)，所以中作了重復(fù)計(jì)數(shù)，所以2m2m。 于是得到不等于是得到不等式式 3k3k2m2m， 即即 k k2m2m/3 3。 根據(jù)歐拉公式，根據(jù)歐拉公式，

45、 。 因此因此 m m3n n6 .232 mmn推論推論 設(shè)設(shè)G G是一個(gè)（是一個(gè)（n，m）的連通平面圖。）的連通平面圖。（1）若每個(gè)面至少由三條邊圍成，則）若每個(gè)面至少由三條邊圍成，則m3n6；（2）若每個(gè)面至少由四條邊圍成，則）若每個(gè)面至少由四條邊圍成，則m 2n4。例例4 4 利用上述推論判斷利用上述推論判斷 K K5 5 和和 K K3,3 3,3 是否平面圖。是否平面圖。解解 在在 K K5 5 中中 n=5n=5，m=10m=10，3n3n6=96=9。 顯然顯然 m m 3n3n6 6，因此，因此 K K5 5 不是平面圖。不是平面圖。 在圖在圖 K K3, 3 3, 3 中中

46、 n=6n=6，m=9m=9，3n3n6=126=12，因此，因此 m3n m3n6 6，故據(jù)此無(wú)法判斷，故據(jù)此無(wú)法判斷 K K3,3 3,3 是否平面圖。是否平面圖。 但是，注意到但是，注意到 K K3,3 3,3 是二部圖，其每個(gè)面必由是二部圖，其每個(gè)面必由 4 4 條或更多偶數(shù)條邊圍成，則應(yīng)滿足條或更多偶數(shù)條邊圍成，則應(yīng)滿足m2nm2n4 4，但它并不滿足，因此但它并不滿足，因此K K3,33,3也不是平面圖。也不是平面圖。例例4 4 利用上述推論判斷利用上述推論判斷 K K5 5 和和 K K3,3 3,3 是否平面圖。是否平面圖。 3 3庫(kù)拉托斯基定理判別法庫(kù)拉托斯基定理判別法定義定

47、義 邊的剖分，圖邊的剖分，圖G的的剖分圖剖分圖邊的收縮，圖邊的收縮，圖G的的收縮圖收縮圖 定理定理（Kuratowski,1930） 一個(gè)圖一個(gè)圖G G是平面圖的充要條件是是平面圖的充要條件是G G中既不含中既不含K K5 5的剖的剖分圖，也不含分圖，也不含K K3,33,3的剖分圖。的剖分圖。 定理定理（Wagner,1937） 一個(gè)圖一個(gè)圖G G是平面圖的充要條件是是平面圖的充要條件是G G中既沒(méi)有可收縮中既沒(méi)有可收縮到到K K5 5的子圖，也沒(méi)有可收縮到的子圖，也沒(méi)有可收縮到K K3,33,3的子圖。的子圖。解法一解法一 （1 1）去掉邊）去掉邊aa，cc，aa，dd，dd，ee，bb，

48、ee例例5 5 判斷下圖判斷下圖G G是否平面圖。是否平面圖。圖圖G GG G子圖子圖G G1 解法二解法二 （1 1）去掉邊）去掉邊dd，ff和和ee，gg G G子圖子圖G G2 2 2判別下圖是否平面圖。判別下圖是否平面圖。 ( )N練習(xí)練習(xí)8-88-8 1 1用簡(jiǎn)單、直觀判別法判斷下圖所給出的用簡(jiǎn)單、直觀判別法判斷下圖所給出的 兩個(gè)圖是否平面圖。兩個(gè)圖是否平面圖。( )( )YY8.9 8.9 有向圖有向圖 一、有向圖的定義及表示一、有向圖的定義及表示二、與無(wú)向圖類似的概念二、與無(wú)向圖類似的概念三、與無(wú)向圖類似的性質(zhì)三、與無(wú)向圖類似的性質(zhì) 例例1 1 設(shè)設(shè)G=（V，E），），V=v1，

49、v2，v3，v4， E= ， 則則G是一個(gè)有向圖。是一個(gè)有向圖。),v,v (),v,v (),v,v (),v,v (),v,v (4313234121)v,v(14定義定義 有向圖有向圖G G是一個(gè)有序二元組（是一個(gè)有序二元組（V V，E E），其中結(jié)點(diǎn)集），其中結(jié)點(diǎn)集V V是一有限非空集合，邊集是一有限非空集合，邊集E E是是V V中不同元素的中不同元素的有序有序?qū)ε嫉膶?duì)偶的集合。集合。一、有向圖的定義及表示一、有向圖的定義及表示圖解表示：圖解表示：10111011000010114321vvvvP1 1鄰接矩陣，可達(dá)矩陣鄰接矩陣，可達(dá)矩陣00011011000010104321vvvv

50、A鄰接矩陣鄰接矩陣可達(dá)矩陣可達(dá)矩陣二、與無(wú)向圖類似的概念二、與無(wú)向圖類似的概念 例例2 2 利用下圖的鄰接矩陣?yán)孟聢D的鄰接矩陣A求其可達(dá)矩陣求其可達(dá)矩陣P。1010101100000001000110110000101000011011000010102A000110110000101010101011000000010001101100001010A3101010110000000100011011000010100001101100001010A42022404400002022AAAAB432將將B B中非零元素改為中非零元素改為1 1，得可達(dá)矩陣，得可達(dá)矩陣P P與前面結(jié)果相同與前面

51、結(jié)果相同解解 在有向圖中從在有向圖中從vi到到vj可達(dá)，并不意味著從可達(dá)，并不意味著從vj到到vi也可達(dá)；也可達(dá)； 即便從即便從vi到到vj可達(dá)，從可達(dá)，從vj到到vi也可達(dá)，也可達(dá)， d(vi，vj) 與與 d(vj，vi) 也不一定相等。也不一定相等。2 2路、開(kāi)路、回路、真路和環(huán)路、開(kāi)路、回路、真路和環(huán)3 3可達(dá)、短程和距離可達(dá)、短程和距離注：注： 4 4結(jié)點(diǎn)的度結(jié)點(diǎn)的度 結(jié)點(diǎn)結(jié)點(diǎn)v v的出度，記作的出度，記作degdeg+ +(v);(v); 結(jié)點(diǎn)結(jié)點(diǎn)v v的入度，記作的入度，記作degdeg(v);(v); 結(jié)點(diǎn)結(jié)點(diǎn)v v度，用度，用 deg(v)deg(v)表示表示, , n1ii

52、m2)vdeg(m)v(deg)v(degn1iin1ii deg(v)=degdeg(v)=deg+ +(v)+ deg(v)+ deg(v)(v) 5 5連通性連通性 定義定義 弱連通弱連通； 單向連通單向連通； 強(qiáng)連通強(qiáng)連通。 例例3 3 弱連通弱連通單向連通單向連通強(qiáng)連通強(qiáng)連通6 6子圖、真子圖和生成子圖子圖、真子圖和生成子圖例例4 4 7 7同構(gòu)同構(gòu) 例例5 5三、與無(wú)向圖類似的性質(zhì)三、與無(wú)向圖類似的性質(zhì)定理定理8-308-30 設(shè)設(shè)G G是具有是具有n n個(gè)結(jié)點(diǎn)和鄰接矩陣個(gè)結(jié)點(diǎn)和鄰接矩陣A A的有向的有向圖，則圖，則A Al（l=1, 2, =1, 2, ）的第）的第i i行行j

53、j列的元素表示從結(jié)點(diǎn)列的元素表示從結(jié)點(diǎn)v vi i到到v vj j長(zhǎng)為長(zhǎng)為 l 的有向路的條數(shù)。的有向路的條數(shù)。定理定理8-298-29 設(shè)設(shè)G G是具有是具有n n個(gè)結(jié)點(diǎn)的有向圖，若從結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的有向圖，若從結(jié)點(diǎn)v vi i到到v vj j可達(dá)，則其短程是一條長(zhǎng)度不大于可達(dá)，則其短程是一條長(zhǎng)度不大于n n1的真路。的真路。定理定理8-318-31 一個(gè)連通（弱連通）有向圖具有歐拉一個(gè)連通（弱連通）有向圖具有歐拉回路的充要條件是回路的充要條件是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)的入度等于出度。對(duì)于這兩個(gè)結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)的出度比入度等于出度。對(duì)于這兩個(gè)結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)的出度比入度多入度多1 1，另一個(gè)結(jié)點(diǎn)的出度比入度少，另一個(gè)結(jié)點(diǎn)的出度比入度少1 1。 例例6練習(xí)練習(xí) 8-98-9 1. 對(duì)下圖回答以下問(wèn)題，在相應(yīng)題目后面的括號(hào)中鍵入對(duì)下圖回答以下問(wèn)題，在相應(yīng)題目后面的括號(hào)中鍵入你的答案。你的答案。 （1）由）由b到到e的短程是的短程是 （ ） （2）由）由b到到e的路的條數(shù)是：的路的條數(shù)是：A. 1條；條；B. 3