1、1 1第六章第六章 圖圖 論論 在第二章討論關(guān)系時，我們曾經(jīng)引進過圖的一些概念。在第二章討論關(guān)系時，我們曾經(jīng)引進過圖的一些概念。在那里，圖只是作為表達集合上二元關(guān)系的一種工具。在那里，圖只是作為表達集合上二元關(guān)系的一種工具。在這一章我們對無向圖的基本概念、基本性質(zhì)、各種特在這一章我們對無向圖的基本概念、基本性質(zhì)、各種特殊的圖及其判別方法進行較為詳細的討論。最后將無向殊的圖及其判別方法進行較為詳細的討論。最后將無向圖的概念和性質(zhì)推廣到有向圖。由于學時有限，我們只圖的概念和性質(zhì)推廣到有向圖。由于學時有限，我們只介紹最基本的內(nèi)容。介紹最基本的內(nèi)容。 主要內(nèi)容如下主要內(nèi)容如下 6.1 6.1 圖的基本

2、概念圖的基本概念 6.5 6.5 二部圖二部圖 6.2 6.2 圖的矩陣表示圖的矩陣表示 6.6 6.6 平面圖平面圖 6.3 6.3 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖 6.7 6.7 有向圖有向圖 6.4 6.4 樹樹 6.8 6.8 有向樹有向樹2 26.1 6.1 圖的基本概念圖的基本概念 一、圖的定義及其表示一、圖的定義及其表示 1. 1. 圖的定義圖的定義 定義定義6-16-1 圖圖G G是一個有序二元組（是一個有序二元組（V V，E E），其中），其中V=vV=v1 1，v v2 2，v vn n 是一個有限非空的集合。是一個有限非空的集合。V V中的元素稱中的元素稱為為G G

3、的結(jié)點，的結(jié)點，V V稱為圖稱為圖G G的結(jié)點集，常記作的結(jié)點集，常記作V V（G G）；）； E E是是V V中不同元素的非有序?qū)ε嫉募希胁煌氐姆怯行驅(qū)ε嫉募希珽 E中的元素稱中的元素稱為為G G的邊，的邊，E E稱為圖稱為圖G G的邊集，常記作的邊集，常記作E E（G G）。）。 例例1 設(shè)設(shè) V =vV =v1 1，v v2 2，v v3 3，v v4 4，v v5 5, E = E = 則則 G=G=（V V，E E）是一個圖。）是一個圖。,4342323121vvvvvvvvvvv,v,v,v54533 3 2. 2. 圖的表示方法圖的表示方法 圖解表示法圖解表示法 一個圖

4、可以用平面上的一個圖解來表示。用平面上一個圖可以用平面上的一個圖解來表示。用平面上的一些點分別表示圖的結(jié)點，用連接相應(yīng)兩個結(jié)點而不的一些點分別表示圖的結(jié)點，用連接相應(yīng)兩個結(jié)點而不經(jīng)過其它結(jié)點的直線（或曲線）來表示圖的邊。經(jīng)過其它結(jié)點的直線（或曲線）來表示圖的邊。 矩陣表示法矩陣表示法 用矩陣的方法也可以表示一個圖。在用矩陣的方法也可以表示一個圖。在6.26.2節(jié)中我們再專節(jié)中我們再專門討論。門討論。 例例2 2 (a).(b) (a).(b)分別給出了例分別給出了例1 1中圖中圖G G的圖解方法。的圖解方法。4 4 二、完全圖與補圖二、完全圖與補圖 1 1（n n，m m）圖）圖: : 2 2

5、兩結(jié)點是相鄰接的：兩結(jié)點是相鄰接的： 3 3邊和結(jié)點是關(guān)聯(lián)的：邊和結(jié)點是關(guān)聯(lián)的： 4 4孤立點孤立點 5 5兩條邊是鄰接的：兩條邊是鄰接的： 6 6孤立邊孤立邊 定義定義6-26-2 在圖在圖G G中，如果任意兩個不同的結(jié)中，如果任意兩個不同的結(jié)點都是鄰接的，則稱圖點都是鄰接的，則稱圖G G是完全圖。是完全圖。 例例3 3 圖圖6-26-2分別給出了一個結(jié)點、二個結(jié)點、三分別給出了一個結(jié)點、二個結(jié)點、三個結(jié)點、四個結(jié)點和五個結(jié)點的完全圖。個結(jié)點、四個結(jié)點和五個結(jié)點的完全圖。5 5 定義定義6-36-3 圖圖G G的補圖是由的補圖是由G G的所有結(jié)點和為了使的所有結(jié)點和為了使G G成為完全圖所需

6、添加的那些邊組成的圖，用成為完全圖所需添加的那些邊組成的圖，用 表示。表示。G 例例4 4 圖圖6-36-3中（中（b b）所表示的圖是（）所表示的圖是（a a）圖的補圖。）圖的補圖。圖圖6-46-4給出了圖給出了圖6-16-1的補圖。的補圖。6 6 三、連通圖三、連通圖 1 1結(jié)點的度：結(jié)點的度： 定理定理6-16-1 設(shè)圖設(shè)圖G G具有結(jié)點集具有結(jié)點集vv1 1，v v2 2，v vn n 和和m m條條邊，則邊，則G G中所有結(jié)點的度之和中所有結(jié)點的度之和 。n1iim2)vdeg( 例如例如 圖圖6-46-4中所有結(jié)點的度之和中所有結(jié)點的度之和剛好是邊數(shù)剛好是邊數(shù)3 3的兩倍。的兩倍。

7、51ii621012)vdeg(7 7 推論推論 任何圖任何圖G G中，度為奇數(shù)的結(jié)點個數(shù)為偶數(shù)。中，度為奇數(shù)的結(jié)點個數(shù)為偶數(shù)。 證明證明 設(shè)圖設(shè)圖G G中，奇數(shù)度結(jié)點集為中，奇數(shù)度結(jié)點集為V V1 1，偶數(shù)度結(jié)點，偶數(shù)度結(jié)點 集為集為V V2 2，邊數(shù)為，邊數(shù)為m m， 則則 于是于是 m2)vdeg()vdeg()vdeg(21VvVvVv21VvVv)vdeg(m2)vdeg( 因為因為 和和2m2m均為偶數(shù)，所以均為偶數(shù)，所以也必為偶數(shù)。由于當也必為偶數(shù)。由于當v v V V1 1時，時，deg(v)deg(v)均為奇數(shù)，均為奇數(shù)，因此因此#V#V1 1必為偶數(shù)。必為偶數(shù)。2Vvv)(

8、deg1Vv)vdeg(8 8 2 2路：圖路：圖G G中中l(wèi) l條邊的序列條邊的序列vv0 0，v v1 1vv1 1，v v2 2vvl11，v vl 稱為連接稱為連接v v0 0到到v vl的一條長為的一條長為 l 的路。它常簡單地用結(jié)點的路。它常簡單地用結(jié)點 的序列的序列v v0 0v v1 1v v2 2vvl11v vl來表示。來表示。 3 3開路：若開路：若v v0 0 v vl，則稱路，則稱路v v0 0v v1 1v v2 2vvl11v vl為開路。為開路。 4 4回路：若回路：若v v0 0=v=vl，則稱路，則稱路v v0 0v v1 1v v2 2vvl11v vl為

9、回路。為回路。 5 5真路：若開路真路：若開路v v0 0v v1 1v v2 2vvl11v vl中，所有結(jié)點互不相同中，所有結(jié)點互不相同 （此時所有邊也互不相同），則稱該路為真路。（此時所有邊也互不相同），則稱該路為真路。 6 6環(huán)：在回路環(huán)：在回路v v0 0v v1 1v v2 2vvl11v v0 0中，若中，若v v0 0，v v1 1，v v2 2，v vl11 各不相同（此時所有邊也互不相同），則稱該回路為環(huán)。各不相同（此時所有邊也互不相同），則稱該回路為環(huán)。 7 7兩結(jié)點是連接的：兩結(jié)點是連接的： 在圖在圖G G中，若存在一中，若存在一 條路連接條路連接v vi i和和v v

10、j j，則稱結(jié)，則稱結(jié) 點點v vi i與與v vj j是連接的是連接的. . 例例5 59 9 定義定義6-46-4 在圖在圖G G中，若任意兩個結(jié)點都是連接的，中，若任意兩個結(jié)點都是連接的，則稱則稱G G是連通圖，否則，稱是連通圖，否則，稱G G為非連通圖。僅有一個孤立為非連通圖。僅有一個孤立結(jié)點的圖定義它為連通圖。結(jié)點的圖定義它為連通圖。 例例6 例例5 5所給出的圖是連通圖。下圖給出的是所給出的圖是連通圖。下圖給出的是 非連通圖。非連通圖。 1010 四、子圖與分圖四、子圖與分圖 利用子集的概念可定義圖利用子集的概念可定義圖G G的子圖。的子圖。 定義定義6-56-5 設(shè)有圖設(shè)有圖G

11、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，則稱，則稱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的生成子圖的生成子圖。 例例7 7 非真非真生成生成真真生成生成真真非生成非生成

12、非真非真非生成非生成真真非生成非生成1111 定義定義6-66-6 設(shè)設(shè)H H是圖是圖G G的子圖，如果的子圖，如果H H滿足以下條件，則滿足以下條件，則稱稱H H是是G G的分圖。的分圖。 （1 1）H H是連通的；是連通的； （2 2）對）對G G的任意子圖的任意子圖G G ，若，若G G H H，且，且H H G G G G，則，則G G 不是連通。不是連通。 例例8 8 對第對第1010頁給出的圖頁給出的圖G G，試判斷（，試判斷（b b）、（）、（c c）、）、（d d）、（）、（e e）各是否）各是否G G的分圖的分圖 解解 （b b）顯然不是）顯然不是G G的分圖。因為（的分圖。

13、因為（b b）不連通。）不連通。 （c）也不是）也不是G的分圖。的分圖。 （d）是）是G的分圖。的分圖。 （e）是）是G的分圖。的分圖。 1212 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 均是割邊，均是割邊， 定理定理6-26-2 在圖在圖G中邊中邊 vi，vj 為割邊的充要條件為割邊的充要條件是邊是邊 vi，vj 不在不在G的任何環(huán)上出現(xiàn)。的任何環(huán)上出現(xiàn)。1 1割點：如果

14、在圖割點：如果在圖G G中刪去結(jié)點中刪去結(jié)點v v（及與其相關(guān)聯(lián)的所（及與其相關(guān)聯(lián)的所有邊后），圖有邊后），圖G G的分圖數(shù)增加，則稱結(jié)點的分圖數(shù)增加，則稱結(jié)點v v是是G G的割點。的割點。 例例1010 下圖中圖中v6，v4均是割點。均是割點。 1313 2 2距離距離：結(jié)點：結(jié)點v vi i和和v vj j間的短程的長度稱為間的短程的長度稱為v vi i和和v vj j間的距離。用間的距離。用d d（v vi i，v vj j）表示。）表示。五、短程和距離五、短程和距離 1 1短程短程：在圖：在圖G G中，結(jié)點中，結(jié)點v vi i和和v vj j若由一條或更多條若由一條或更多條路相連接，

15、則其中必有長度最短的路，稱它為從路相連接，則其中必有長度最短的路，稱它為從v vi i到到v vj j的短程。的短程。 例例1111 3),(1),(2),(612151vvdvvdvvd1414 定理定理6-36-3 設(shè)設(shè)G G是具有結(jié)點集是具有結(jié)點集V= vV= v1 1，v v2 2，v vn n 的圖，則的圖，則對于對于G G中任意兩個相連接的結(jié)點中任意兩個相連接的結(jié)點v vi i，v vj j（v vi i v vj j），其短程是一），其短程是一條長度不大于條長度不大于n1n1的真路。的真路。 證明證明 設(shè)設(shè) 為任一連接為任一連接v vi i到到v vj j的路，的路，且且 = v

16、= vi iu u1 1 u u2 2uur ruuk kuul11v vj j，若，若 中有相同的結(jié)點，設(shè)為中有相同的結(jié)點，設(shè)為u ur r= u= uk k（rkr2n2S2n2，也與，也與S=2n2S=2n2矛盾。矛盾。 由上可知，由上可知，T T中至少有兩片樹葉。中至少有兩片樹葉。3636 樹的有些性質(zhì)可用來作為樹的定義，我樹的有些性質(zhì)可用來作為樹的定義，我們列出下面三條：們列出下面三條： （1 1）每兩個結(jié)點間由唯一的真路相連接）每兩個結(jié)點間由唯一的真路相連接的圖是樹；的圖是樹； （2 2）m=n1m=n1的連通圖是樹；的連通圖是樹； (3(3）m=n1m=n1且無環(huán)的圖是樹。且無環(huán)

17、的圖是樹。3737 三、生成樹與最小生成樹三、生成樹與最小生成樹 1 1生成樹生成樹 定義定義6-146-14 若連通圖若連通圖G G的生成子圖的生成子圖T T是一棵樹，則是一棵樹，則稱稱T T為為G G的生成樹。的生成樹。 例例4 4 下下圖中（圖中（b b）和（）和（c c）都是（）都是（a a）的生成樹。）的生成樹。 3838 2 2構(gòu)造連通圖構(gòu)造連通圖G=G=（V V，E E）的生成樹的方法）的生成樹的方法 （a a）破環(huán)法）破環(huán)法 例例5 5 用破環(huán)法，構(gòu)造上頁圖（用破環(huán)法，構(gòu)造上頁圖（a a）的生成樹的過程如下：）的生成樹的過程如下： 3939 （b b）避環(huán)法）避環(huán)法例例6 6

18、用避環(huán)法構(gòu)造（用避環(huán)法構(gòu)造（a a）的生成樹過程如下：）的生成樹過程如下：4040 3 3最小生成樹最小生成樹 定義定義6-156-15 每條邊都以實數(shù)賦權(quán)的圖稱為帶權(quán)圖。每條邊都以實數(shù)賦權(quán)的圖稱為帶權(quán)圖。 例例8 8 下下圖是一連通帶權(quán)圖。圖是一連通帶權(quán)圖。 當當G G是一帶權(quán)圖時，常將其表示為有序三元組是一帶權(quán)圖時，常將其表示為有序三元組G=G=（V V，E E，f f），），這里這里f f是一由邊集是一由邊集E E到實數(shù)集到實數(shù)集R R的函數(shù)的函數(shù) f f：E ER.R.4141 定義定義6-166-16 設(shè)設(shè)G=（V，E，f）是一連通帶權(quán)）是一連通帶權(quán)圖，圖，T是是G的一棵生成樹，的一

19、棵生成樹，T的邊集用的邊集用E（T）表示，）表示，T的的各邊權(quán)值之和各邊權(quán)值之和W（T）= 稱為稱為T的權(quán)。的權(quán)。G的所的所有生成樹中權(quán)最小的生成樹稱為有生成樹中權(quán)最小的生成樹稱為G的最小生成樹。的最小生成樹。)T(Ee)e(f 例例9 9 它們的權(quán)它們的權(quán)W（T1）=24，W（T2）=30。4242 4 4構(gòu)造連通帶權(quán)圖構(gòu)造連通帶權(quán)圖G=G=（V V，E E，f f）的最小生成樹）的最小生成樹的方法的方法 例例1010 以例以例8中圖為例，中圖為例， （1 1） 破環(huán)法破環(huán)法 G=G1G2G3G4G5G6=T0W(T0)=184343 （2 2） 避環(huán)法避環(huán)法G=G1G1G2G3G4G5 =

20、 T04444練習練習6-46-4 1 1設(shè)樹設(shè)樹T T有有7 7條邊，問條邊，問T T有多少個結(jié)點？（有多少個結(jié)點？（ ） 2 2設(shè)設(shè)G G是一個樹林，由是一個樹林，由3 3個分圖組成，若個分圖組成，若G G有有1515個結(jié)點，個結(jié)點，問問G G有多少條邊？（有多少條邊？（ ） 3 3互不同構(gòu)的互不同構(gòu)的2 2結(jié)點樹有（結(jié)點樹有（ ）棵？）棵？ 互不同構(gòu)的互不同構(gòu)的4 4結(jié)點樹有（結(jié)點樹有（ ）棵？）棵？8 812121 12 22424 4求下圖給出的帶權(quán)圖的最小生成樹的權(quán)（求下圖給出的帶權(quán)圖的最小生成樹的權(quán)（ ） 4545 6.5 6.5 二部圖二部圖 一、二部圖一、二部圖 定義定義6-

21、176-17 若一個圖若一個圖G G的結(jié)點集的結(jié)點集V V能劃為兩個子集能劃為兩個子集V V1 1和和V V2 2，使得，使得G G的每一條邊的每一條邊vvi i，v vj j 滿足滿足v vi i V V1 1，v vj j V V2 2，則稱，則稱G G是一個是一個二部圖，二部圖，V V1 1和和V V2 2稱為稱為G G的互補結(jié)點子集。此時可將的互補結(jié)點子集。此時可將G G記作記作G=G=（V V1 1，V V2 2，E E）。）。 若若V V1 1中任一結(jié)點與中任一結(jié)點與V V2 2中每一結(jié)點均有邊相連接，則稱二部中每一結(jié)點均有邊相連接，則稱二部圖為完全二部圖。若圖為完全二部圖。若#V

22、#V1 1=r=r，#V#V2 2=t=t，則記完全二部圖，則記完全二部圖G G為為K Kr, tr, t。例例V V4 44646 例例1 1 下圖中的圖是否是二部圖？下圖中的圖是否是二部圖？4747(a)(a)(b)(b)(c)(c)4848二部圖不一定是連通圖。二部圖不一定是連通圖。定理定理6-136-13 圖圖G G為二部圖的充要條件是為二部圖的充要條件是G G的所的所有回路均為偶數(shù)長。有回路均為偶數(shù)長。 4949二、匹配二、匹配 定義定義6-18 6-18 設(shè)設(shè)G G是具有互補結(jié)點子集是具有互補結(jié)點子集V V1 1和和V V2 2的二部的二部圖，其中圖，其中V V1 1=v=v1 1

23、，v v2 2，v vr r ，V V1 1對對V V2 2的匹配是的匹配是G G的一個子的一個子圖，它由圖，它由r r條邊條邊vv1 1，v v 1 1 ，vv2 2，v v 2 2 ，vvr r，v v r r 組成，組成，其中，其中，v v 1 1，v v 2 2，v v r r是是V V2 2中中r r個不同的元素個不同的元素。 例例2 2 下圖所給出的二部圖是否存在圖所給出的二部圖是否存在V V1 1對對V V2 2的匹的匹配？是否存在配？是否存在V V2 2對對V V1 1的匹配？的匹配？5050 例例3 3 某班級成立了三個運動隊：籃球隊、排球隊某班級成立了三個運動隊：籃球隊、排

24、球隊和足球隊。今有張、王、李、趙、陳和足球隊。今有張、王、李、趙、陳5 5名同學，若已知張、名同學，若已知張、王為籃球隊員；張、李、趙為排球隊員；李、趙、陳為足王為籃球隊員；張、李、趙為排球隊員；李、趙、陳為足球隊員，問能否從這球隊員，問能否從這5 5人中選出人中選出3 3名不兼職的隊長？名不兼職的隊長？在圖中存在在圖中存在V V1 1對對V V2 2的匹配，因此題目的要求可以滿足。的匹配，因此題目的要求可以滿足。 解解構(gòu)造二部圖構(gòu)造二部圖G=G=（V V1 1，V V2 2，E E），）， V V1 1V V2 25151N N練習練習6-56-5 1 1在括號中鍵入在括號中鍵入“Y”Y”或

25、或“N”N”回答相應(yīng)的問題。回答相應(yīng)的問題。 （1 1）圖）圖(a)(a)是否為二部圖？（是否為二部圖？（ ） 若是，找出它的互補結(jié)點子集：若是，找出它的互補結(jié)點子集： V V1 1= = V V2 2= = (a)(a) (b)(b) （2 2）圖）圖(b)(b)是否為二部圖？（是否為二部圖？（ ） Y Yv v1 1，v v3 3，v v5 5，v v6 6v v2 2，v v4 4，v v7 752526.6 6.6 平面圖平面圖 一、平面圖的定義一、平面圖的定義 定義定義6-196-19 一個圖一個圖G G若能畫在平面上，它的邊除在若能畫在平面上，它的邊除在端點處外互不交叉，則稱端點處

26、外互不交叉，則稱G G為平面圖。畫出的沒有邊交叉為平面圖。畫出的沒有邊交叉的圖解稱為的圖解稱為G G的一個平面嵌入。的一個平面嵌入。 例例1 1 圖（圖（a a）是平面圖，（）是平面圖，（b b）是該圖的一個平面）是該圖的一個平面嵌入。嵌入。5353 二、平面圖的判別二、平面圖的判別 1 1簡單、直觀判別法簡單、直觀判別法 設(shè)設(shè)G G是畫于平面上的一個圖，是畫于平面上的一個圖， =v=v1 1 v v2 2 v v3 3 v v4 4 v v1 1是是G G中任意一個環(huán)。中任意一個環(huán)。 = v= v1 1vv3 3和和=v=v2 2vv4 4是是G G中任意兩中任意兩條邊無公共結(jié)點的真路。條邊

27、無公共結(jié)點的真路。 我們往往可以用觀察的方法來判別一個圖是否為平我們往往可以用觀察的方法來判別一個圖是否為平面圖。面圖。5454 例例2 2 用上述簡單、直觀的方法判別下圖中的兩用上述簡單、直觀的方法判別下圖中的兩圖是否平面圖。圖是否平面圖。 5555 2. 2. 歐拉公式判斷法歐拉公式判斷法 定義定義6-206-20 設(shè)設(shè)G G是一個連通平面圖，是一個連通平面圖，G G的邊將的邊將G G所在的平面劃分成若干個區(qū)域，每一個區(qū)域稱為所在的平面劃分成若干個區(qū)域，每一個區(qū)域稱為G G的一的一個個面面。其中面積無限的區(qū)域稱為。其中面積無限的區(qū)域稱為無限面無限面。面積有限的區(qū)。面積有限的區(qū)域稱為域稱為有

28、限面有限面。包圍每個面的所有邊構(gòu)成的回路稱為面。包圍每個面的所有邊構(gòu)成的回路稱為面的的邊界邊界。 例例3 3 5656 定理定理6-146-14 設(shè)設(shè)G G是一連通平面圖，有是一連通平面圖，有n n個結(jié)點，個結(jié)點，m m條邊，條邊，K K個面，則個面，則 nm+K=2nm+K=2此定理中的公式稱為歐拉公式。此定理中的公式稱為歐拉公式。 證明證明 （對邊數(shù)（對邊數(shù)m m進行歸納）進行歸納） 當當m=0m=0和和m=1m=1時，定理顯然成立。時，定理顯然成立。 假設(shè)定理對假設(shè)定理對m1m1條邊的任何連通平面圖均成立，設(shè)條邊的任何連通平面圖均成立，設(shè)G G是一是一具有具有n n個結(jié)點，個結(jié)點，m m

29、條邊，條邊，K K個面的連通平面圖（個面的連通平面圖（m2m2） 由歸納假設(shè)由歸納假設(shè)G G 中歐拉公式成立。中歐拉公式成立。 因此因此nn（m1m1）+ +（K1K1）=2=2，即，即nm+K=2nm+K=2。 若若G中沒有環(huán)，則中沒有環(huán)，則G是一棵樹，是一棵樹，K=1，且，且m=n1，于是，于是nm+K=n（n1）+1=2。 若若G G中有環(huán)，則去掉中有環(huán)，則去掉G G的任一環(huán)上的一條邊的任一環(huán)上的一條邊e e，剩下的圖，剩下的圖G G 仍連通，有仍連通，有n n個結(jié)點，個結(jié)點，K1K1個面，個面，m1m1條邊，條邊， 5757 定理定理6-156-15 設(shè)設(shè)G G是一（是一（n n，m

30、m）的連通平面圖，）的連通平面圖，m2m2， 則則 m3n6 m3n6 （* *） 證明證明 當當m=2m=2時，因時，因G G是簡單圖必無環(huán)，是簡單圖必無環(huán)， 所以所以n=3n=3， 上式成立。上式成立。 當當m2m2時，每個面至少由三條邊圍成，因此各面時，每個面至少由三條邊圍成，因此各面邊界的邊數(shù)之和邊界的邊數(shù)之和3K3K。 另一方面，因為有些邊同時在兩個面的邊界中，在另一方面，因為有些邊同時在兩個面的邊界中，在中作了重復計數(shù)，所以中作了重復計數(shù)，所以2m2m。 于是得到不等式于是得到不等式 3K2m， 即即 K2m/3。 根據(jù)歐拉公式，根據(jù)歐拉公式， 。 因此因此 m3n6232 mmn

31、5858 圖圖K K3, 33, 3中中n=6n=6，m=9m=9，3n6=123n6=12。因此因此 m3n6m3n6。滿足（。滿足（* *）式，故無法判定）式，故無法判定K K3,33,3是非是非平面圖。平面圖。 例例4 4 利用定理利用定理6-156-15判別圖下圖中的判別圖下圖中的K K5 5和和K K3,33,3是否非平是否非平面圖。面圖。 解解 圖圖K K5 5中中n=5n=5，m=10m=10，3n6=93n6=9。 顯然顯然m m 3n63n6。因此。因此k k5 5不是平面圖。不是平面圖。 實際上，利用實際上，利用K K3,33,3是二部圖，是二部圖，可以證明，如果它是平面圖

32、，可以證明，如果它是平面圖，則應(yīng)滿足則應(yīng)滿足m2n4m2n4，但它并不，但它并不滿足。滿足。 因此因此K K3,33,3不是平面圖。不是平面圖。5959 3 3庫拉托斯基定理判別法庫拉托斯基定理判別法 定義定義6-216-21 如果兩個圖如果兩個圖G G1 1和和G G2 2是同構(gòu)的，或者通是同構(gòu)的，或者通過反復插入或刪除度為過反復插入或刪除度為2 2的結(jié)點，它們能變成同構(gòu)的圖，的結(jié)點，它們能變成同構(gòu)的圖，則稱則稱G G1 1和和G G2 2在度為在度為2 2的結(jié)點內(nèi)同構(gòu)。的結(jié)點內(nèi)同構(gòu)。6060 定理定理6-166-16 （庫拉托斯基定理）（庫拉托斯基定理） 一個圖是平面圖的充要條件是它不包含

33、在度為一個圖是平面圖的充要條件是它不包含在度為2 2的的結(jié)點內(nèi)與結(jié)點內(nèi)與K K5 5同構(gòu)的子圖，也不包含在度為同構(gòu)的子圖，也不包含在度為2 2的結(jié)點內(nèi)與的結(jié)點內(nèi)與K K3,33,3同構(gòu)的子圖。同構(gòu)的子圖。 解法一解法一 （1 1）去掉圖）去掉圖G G中邊中邊 aa，cc，aa，dd，dd，ee，bb，ee， 例例5 5 利用定理利用定理6-166-16判別圖判別圖G G是否非平面圖。是否非平面圖。圖圖G G6161 解法二解法二 （1 1）去掉圖）去掉圖6-566-56中邊中邊dd，ff和和ee，gg， 6262 2 2用庫拉托斯基定理判別下圖是否平面圖。用庫拉托斯基定理判別下圖是否平面圖。

34、( )N練習練習6-66-6 1 1用簡單、直觀判別法判斷下圖所給出的用簡單、直觀判別法判斷下圖所給出的 兩個圖是否平面圖。兩個圖是否平面圖。( )( )YY63636.7 6.7 有向圖有向圖 一、有向圖的定義及表示一、有向圖的定義及表示 定義定義6-226-22 有向圖有向圖G G是一個有序二元組（是一個有序二元組（V V，E E），），其中結(jié)點集其中結(jié)點集V V是一有限非空集合，邊集是一有限非空集合，邊集E E是是V V中不同元素的中不同元素的有序?qū)ε嫉募稀Ｓ行驅(qū)ε嫉募稀?例例1 1 設(shè)設(shè)G=（V，E），），V=v1，v2，v3，v4， E= ， 則則G是一個有向圖。是一個有向圖。)

35、,v,v (),v,v (),v,v (),v,v (),v,v (4313234121)v,v(146464 例例3 3 用鄰接矩陣用鄰接矩陣A A表示例表示例1 1中的有向圖中的有向圖G G如下：如下： 000110110000101043214321vvvvAvvvv 例例2 2 用圖解法表示例用圖解法表示例1中的圖中的圖G如下圖所示。如下圖所示。6565 定義定義6-236-23 在有向圖在有向圖G=G=（V V，E E）中，若存在一）中，若存在一條從結(jié)點條從結(jié)點v vi i到結(jié)點到結(jié)點v vj j的有向路，則稱從的有向路，則稱從v vi i到到v vj j是可達的。是可達的。 在有向

36、圖中從在有向圖中從v vi i到到v vj j可達，并不意味著從可達，并不意味著從v vj j到到v vi i也可達。也可達。 即便從即便從v vi i到到v vj j可達，從可達，從v vj j到到v vi i也可達，也可達，d d（v vi i，v vj j）與）與d d（v vj j，v vi i）也不一定相等。）也不一定相等。 二、與無向圖類似的概念二、與無向圖類似的概念 無向圖中的概念大都可推廣到有向圖。下面介紹無向圖中的概念大都可推廣到有向圖。下面介紹一些主要的概念。一些主要的概念。 1 1路、開路、回路、真路和環(huán)路、開路、回路、真路和環(huán) 2 2可達、短程和距離可達、短程和距離66

37、66 3 3可達矩陣可達矩陣 例如，下圖的可達矩陣例如，下圖的可達矩陣1011101100001011vvvvP43216767 例例4 4 利用下圖的鄰接矩陣利用下圖的鄰接矩陣A求其可達矩陣求其可達矩陣P。 解解1010101100000001000110110000101000011011000010102A000110110000101010101011000000010001101100001010A3101010110000000100011011000010100001101100001010A42022404400002022AAAAB432將將B B中非零元素改為中非零元素改為

38、1 1，得可達矩陣，得可達矩陣P P與前面結(jié)果相同與前面結(jié)果相同6868 4 4結(jié)點的度結(jié)點的度 結(jié)點結(jié)點v v的出度，記作的出度，記作degdeg+ +（v v）。）。 v v的入度，記作的入度，記作degdeg（v v）。）。 結(jié)點結(jié)點v v的出度與入度之和稱為的出度與入度之和稱為v v的度，的度，用用degdeg（v v）表示。）表示。 有向圖中，有向圖中， ，且且 。n1iim2)vdeg(m)v(deg)v(degn1iin1ii6969 5 5連通性連通性 定義定義6-246-24 在有向圖在有向圖G G中，如果略去邊的方向，中，如果略去邊的方向，將其看作無向圖時，將其看作無向圖時

39、，G G是連通的，則稱是連通的，則稱G G是連通的或是連通的或弱連弱連通通的；如果對于任意兩個結(jié)點，至少有一個結(jié)點到另一的；如果對于任意兩個結(jié)點，至少有一個結(jié)點到另一個結(jié)點是可達的，則稱個結(jié)點是可達的，則稱G G是是單向連通單向連通的；如果對于任意兩的；如果對于任意兩個結(jié)點，兩者之間是相互可達的，則稱個結(jié)點，兩者之間是相互可達的，則稱G G是是強連通強連通的。的。 例例5 5 弱連通弱連通單向連通單向連通強連通強連通7070 6 6子圖、真子圖和生成子圖子圖、真子圖和生成子圖 例例6 6 7171 7 7同構(gòu)同構(gòu) 例例7 77272 三、與無向圖類似的性質(zhì)三、與無向圖類似的性質(zhì) 定理定理6-1

40、76-17 設(shè)設(shè)G G是具有是具有n n個結(jié)點的有向圖，若從結(jié)個結(jié)點的有向圖，若從結(jié)點點v vi i到到v vj j可達，則其短程是一條長度不大于可達，則其短程是一條長度不大于n n1的真路。的真路。 定理定理6-186-18 設(shè)設(shè)G G是具有是具有n n個結(jié)點和鄰接矩陣個結(jié)點和鄰接矩陣A A的有的有向圖，則向圖，則A Al（l=1, 2, =1, 2, ）的第）的第i i行行j j列的元素表示從結(jié)列的元素表示從結(jié)點點v vi i到到v vj j長為長為 l 的路的條數(shù)。的路的條數(shù)。7373 定理定理6-196-19 一個連通（弱連通）有向圖具有歐一個連通（弱連通）有向圖具有歐拉回路的充要條件

41、是拉回路的充要條件是G G的每一個結(jié)點的入度和出度相等。的每一個結(jié)點的入度和出度相等。具有歐拉路的充要條件是除兩個結(jié)點外，每個結(jié)點的具有歐拉路的充要條件是除兩個結(jié)點外，每個結(jié)點的入度等于出度。對于這兩個結(jié)點，一個結(jié)點的出度比入度等于出度。對于這兩個結(jié)點，一個結(jié)點的出度比入度多入度多1 1，另一個結(jié)點的出度比入度少，另一個結(jié)點的出度比入度少1 1。 例例87474練習練習6-76-7 1. 對下圖回答以下問題，在相應(yīng)題目后面的括號中鍵入對下圖回答以下問題，在相應(yīng)題目后面的括號中鍵入你的答案。你的答案。 （1）由）由b到到e的短程是的短程是 （ ） （2）由）由b到到e的路的條數(shù)是：的路的條數(shù)是：

42、A. 1條；條；B. 3條；條；C. 無數(shù)條無數(shù)條 （ ） （3）寫出從）寫出從g到到e的一條非真路的一條非真路 （ ） （4） deg+（e）=（ ） （5） deg（e）=（ ） （6） deg（e）= （ ） （7） d（a，f）=（ ） d（f，a）=（ ）bagebageC Cgfedcegfedce1 13 34 42 25 575756.8 6.8 有向樹有向樹一、有向樹的定義一、有向樹的定義 定義定義6-256-25 一個不包含環(huán)的有向圖一個不包含環(huán)的有向圖G G，若它只，若它只有一個結(jié)點有一個結(jié)點v v0 0的入度為的入度為0 0，而其它所有結(jié)點的入度都等，而其它所有結(jié)點的入

43、度都等于于1 1，則稱，則稱G G是有向樹，是有向樹，v v0 0稱為樹的根。稱為樹的根。 一個孤立的結(jié)點也是一棵有向樹。一個孤立的結(jié)點也是一棵有向樹。 例例1 1 下下 圖給出的圖是否有向樹？圖給出的圖是否有向樹？一級結(jié)點二級結(jié)點三級結(jié)點7676 二、有向樹中的一些概念二、有向樹中的一些概念 （1 1）樹葉）樹葉 （2 2）分枝結(jié)點）分枝結(jié)點 （3 3）兒子、父親、兄弟、祖先和子孫（后代）兒子、父親、兄弟、祖先和子孫（后代） （4 4）以以v v為根的子樹：為根的子樹：設(shè)設(shè)v v是有向樹是有向樹T T的分枝結(jié)點，的分枝結(jié)點，由結(jié)點由結(jié)點v v和它的所有子孫構(gòu)成的結(jié)點集和它的所有子孫構(gòu)成的結(jié)點

44、集V V ，以及從，以及從v v出發(fā)的出發(fā)的所有有向路中的邊構(gòu)成的邊集所有有向路中的邊構(gòu)成的邊集E E 組成組成T T的子圖的子圖T T = =（V V ，E E ）稱為是以稱為是以v v為根的為根的T T的子樹。的子樹。 （5 5）v v的子樹：的子樹：以以v v的兒子為根的子樹。的兒子為根的子樹。 7777 T T1 1又稱為是又稱為是v v0 0的子樹。的子樹。v v0 0的另一棵子樹是以的另一棵子樹是以v v1 1為根為根的子樹的子樹T T2 2= =（vv1 1，v v3 3，v v4 4，v v5 5,（v v1 1,v,v3 3）, ,（v v1 1,v,v4 4），），（v v

45、1 1，v v5 5） ）。）。 子圖子圖T T1 1= =（V V1 1，E E1 1）是以）是以v v2 2為根的子樹。其中為根的子樹。其中 V V1 1= v= v2 2，v v6 6，v v7 7，v v8 8，v v9 9，v v1010 ，E E1 1=（v v2 2，v v6 6），），（v v2 2，v v7 7），（），（v v6 6，v v8 8），（），（v v7 7，v v9 9），（），（v v7 7，v v1010） 。 7878 三、二元樹三、二元樹 定義定義6-266-26 在一有向樹中，若每一結(jié)點的出度在一有向樹中，若每一結(jié)點的出度都小于或等于都小于或等于m

46、m，則稱這棵樹為，則稱這棵樹為m m元樹。若每一個結(jié)點元樹。若每一個結(jié)點的出度恰好等于的出度恰好等于m m或零，則稱這棵樹為完全或零，則稱這棵樹為完全m m元樹。元樹。 例例3 3 二元樹二元樹完全二元樹完全二元樹滿滿二元樹二元樹三元樹三元樹 當當m=2m=2時，分別稱其為二元樹和完全二元樹。若二時，分別稱其為二元樹和完全二元樹。若二元樹的所有樹葉結(jié)點在同一級別則稱它為滿二元樹。元樹的所有樹葉結(jié)點在同一級別則稱它為滿二元樹。7979 定義定義6-276-27 在有向樹中，在有向樹中，若規(guī)定了每一級上結(jié)點的次序，則若規(guī)定了每一級上結(jié)點的次序，則稱這樣的有向樹為有序樹。稱這樣的有向樹為有序樹。 例

47、例4 4 用二元有序樹表示算術(shù)表達式用二元有序樹表示算術(shù)表達式 和和 。)fe (dcbaa)fe(dcb例如例如 右圖（右圖（a a）和（）和（b b）表示）表示兩棵不同的有序樹。兩棵不同的有序樹。解解8080 四、周游二元樹四、周游二元樹 下面介紹周游二元樹常用的三種方法：下面介紹周游二元樹常用的三種方法： 1 1先根周游先根周游 （1 1）訪問根；）訪問根； (2(2）在根的左子樹上執(zhí)行先根周游；）在根的左子樹上執(zhí)行先根周游； （3 3）在根的右子樹上執(zhí)行先根周游。）在根的右子樹上執(zhí)行先根周游。 2 2中根周游中根周游 （1 1）在根的左子樹上執(zhí)行中根周游；）在根的左子樹上執(zhí)行中根周游；

48、 （2 2）訪問根；）訪問根； （3 3）在根的右子樹上執(zhí)行中根周游。）在根的右子樹上執(zhí)行中根周游。 3 3后根周游后根周游 （1 1）在根的左子樹上執(zhí)行后根周游；）在根的左子樹上執(zhí)行后根周游； （2 2）在根的右子樹上執(zhí)行后根周游；）在根的右子樹上執(zhí)行后根周游； （3 3）訪問根。）訪問根。8181 例例5 5 （1 1）用二元有序樹表示算術(shù)表達式）用二元有序樹表示算術(shù)表達式 ) hg (f) ed (c) ba ( （2 2）用三種方法周游此樹，寫出周游結(jié)果。）用三種方法周游此樹，寫出周游結(jié)果。 )gh( f)de(c )ab(先根周游先根周游 )hg(f) ed(c) ba (中根周游中

49、根周游)gh(f)de(c )ab(后根周游后根周游8282五、有向樹中的一些數(shù)量關(guān)系五、有向樹中的一些數(shù)量關(guān)系 有向樹和無向樹一樣，滿足關(guān)系式有向樹和無向樹一樣，滿足關(guān)系式 m = n1 m = n1 定理定理6-206-20 設(shè)設(shè)T T是一棵完全是一棵完全m m元樹，樹葉結(jié)點數(shù)元樹，樹葉結(jié)點數(shù)為為n n0 0，分枝結(jié)點數(shù)為，分枝結(jié)點數(shù)為t t，則（，則（m1m1）t=nt=n0 011。 證明證明 由完全由完全m m元樹的定義知，元樹的定義知，T T的邊數(shù)的邊數(shù)=mt=mt， 結(jié)點數(shù)為結(jié)點數(shù)為 n n0 0+t+t， 于是于是mt=nmt=n0 0+t1 +t1 即即 （m1m1）t=nt

50、=n0 0118383 定理定理6-216-21 設(shè)設(shè)T T是一棵二元樹，是一棵二元樹，n n0 0 表示樹葉結(jié)點數(shù)，表示樹葉結(jié)點數(shù)，n n2 2表示出度為表示出度為2 2的結(jié)點數(shù)，則的結(jié)點數(shù)，則n n0 0 = n= n2 2+1+1。 證明證明 設(shè)設(shè)T T的結(jié)點數(shù)為的結(jié)點數(shù)為n n ，邊數(shù)為，邊數(shù)為m m ，出度為，出度為1 1的的 結(jié)點數(shù)為結(jié)點數(shù)為n n1 1， 則則 n = nn = n0 0+n+n1 1+n+n2 2 m = n1 m = n1 m = nm = n1 1+2n+2n2 2于是于是 n n1 1+2n+2n2 2 = n= n0 0+n+n1 1+n+n2 211 因此因此 n2 = n01 即即 n0 = n2+1。 定理定理6-22 完全二元樹有奇數(shù)個結(jié)點。完全二元樹有奇數(shù)個結(jié)點。 8484練習練習6-86-81計算非同構(gòu)的有向樹的個數(shù)。計算非