1、1 1第六章第六章 圖圖 論論 在第二章討論關系時，我們曾經引進過圖的一些概念。在第二章討論關系時，我們曾經引進過圖的一些概念。在那里，圖只是作為表達集合上二元關系的一種工具。在那里，圖只是作為表達集合上二元關系的一種工具。在這一章我們對無向圖的基本概念、基本性質、各種特在這一章我們對無向圖的基本概念、基本性質、各種特殊的圖及其判別方法進行較為詳細的討論。最后將無向殊的圖及其判別方法進行較為詳細的討論。最后將無向圖的概念和性質推廣到有向圖。由于學時有限，我們只圖的概念和性質推廣到有向圖。由于學時有限，我們只介紹最基本的內容。介紹最基本的內容。 主要內容如下主要內容如下 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、的結點，的結點，V V稱為圖稱為圖G G的結點集，常記作的結點集，常記作V V（G G）；）； E E是是V V中不同元素的非有序對偶的集合，中不同元素的非有序對偶的集合，E E中的元素稱中的元素稱為為G G的邊，的邊，E E稱為圖稱為圖G G的邊集，常記作的邊集，常記作E E（G G）。）。 例例1 設設 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、可以用平面上的一個圖解來表示。用平面上一個圖可以用平面上的一個圖解來表示。用平面上的一些點分別表示圖的結點，用連接相應兩個結點而不的一些點分別表示圖的結點，用連接相應兩個結點而不經過其它結點的直線（或曲線）來表示圖的邊。經過其它結點的直線（或曲線）來表示圖的邊。 矩陣表示法矩陣表示法 用矩陣的方法也可以表示一個圖。在用矩陣的方法也可以表示一個圖。在6.26.2節中我們再專節中我們再專門討論。門討論。 例例2 2 (a).(b) (a).(b)分別給出了例分別給出了例1 1中圖中圖G G的圖解方法。的圖解方法。4 4 二、完全圖與補圖二、完全圖與補圖 1 1（n n，m m）圖）圖: : 2 2

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

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

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

8、deg1Vv)vdeg(8 8 2 2路：圖路：圖G G中中l l條邊的序列條邊的序列vv0 0，v v1 1vv1 1，v v2 2vvl11，v vl 稱為連接稱為連接v v0 0到到v vl的一條長為的一條長為 l 的路。它常簡單地用結點的路。它常簡單地用結點 的序列的序列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中，所有結點互不相同中，所有結點互不相同 （此時所有邊也互不相同），則稱該路為真路。（此時所有邊也互不相同），則稱該路為真路。 6 6環：在回路環：在回路v v0 0v v1 1v v2 2vvl11v v0 0中，若中，若v v0 0，v v1 1，v v2 2，v vl11 各不相同（此時所有邊也互不相同），則稱該回路為環。各不相同（此時所有邊也互不相同），則稱該回路為環。 7 7兩結點是連接的：兩結點是連接的： 在圖在圖G G中，若存在一中，若存在一 條路連接條路連接v vi i和和v v

10、j j，則稱結，則稱結 點點v vi i與與v vj j是連接的是連接的. . 例例5 59 9 定義定義6-46-4 在圖在圖G G中，若任意兩個結點都是連接的，中，若任意兩個結點都是連接的，則稱則稱G G是連通圖，否則，稱是連通圖，否則，稱G G為非連通圖。僅有一個孤立為非連通圖。僅有一個孤立結點的圖定義它為連通圖。結點的圖定義它為連通圖。 例例6 例例5 5所給出的圖是連通圖。下圖給出的是所給出的圖是連通圖。下圖給出的是 非連通圖。非連通圖。 1010 四、子圖與分圖四、子圖與分圖 利用子集的概念可定義圖利用子集的概念可定義圖G G的子圖。的子圖。 定義定義6-56-5 設有圖設有圖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 設設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的分的分圖數增加，則稱邊圖數增加，則稱邊 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的任何環上出現。的任何環上出現。1 1割點：如果

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

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

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

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=G=（V V，E E）的生成樹的方法）的生成樹的方法 （a a）破環法）破環法 例例5 5 用破環法，構造上頁圖（用破環法，構造上頁圖（a a）的生成樹的過程如下：）的生成樹的過程如下： 3939 （b b）避環法）避環法例例6 6

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

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

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

21、176-17 若一個圖若一個圖G G的結點集的結點集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的互補結點子集。此時可將的互補結點子集。此時可將G G記作記作G=G=（V V1 1，V V2 2，E E）。）。 若若V V1 1中任一結點與中任一結點與V V2 2中每一結點均有邊相連接，則稱二部中每一結點均有邊相連接，則稱二部圖為完全二部圖。若圖為完全二部圖。若#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的所的所有回路均為偶數長。有回路均為偶數長。 4949二、匹配二、匹配 定義定義6-18 6-18 設設G G是具有互補結點子集是具有互補結點子集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=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”回答相應的問題。回答相應的問題。 （1 1）圖）圖(a)(a)是否為二部圖？（是否為二部圖？（ ） 若是，找出它的互補結點子集：若是，找出它的互補結點子集： 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簡單、直觀判別法簡單、直觀判別法 設設G G是畫于平面上的一個圖，是畫于平面上的一個圖， =v=v1 1 v v2 2 v v3 3 v v4 4 v v1 1是是G G中任意一個環。中任意一個環。 = v= v1 1vv3 3和和=v=v2 2vv4 4是是G G中任意兩中任意兩條邊無公共結點的真路。條邊

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

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

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

30、m）的連通平面圖，）的連通平面圖，m2m2， 則則 m3n6 m3n6 （* *） 證明證明 當當m=2m=2時，因時，因G G是簡單圖必無環，是簡單圖必無環， 所以所以n=3n=3， 上式成立。上式成立。 當當m2m2時，每個面至少由三條邊圍成，因此各面時，每個面至少由三條邊圍成，因此各面邊界的邊數之和邊界的邊數之和3K3K。 另一方面，因為有些邊同時在兩個面的邊界中，在另一方面，因為有些邊同時在兩個面的邊界中，在中作了重復計數，所以中作了重復計數，所以2m2m。 于是得到不等式于是得到不等式 3K2m， 即即 K2m/3。 根據歐拉公式，根據歐拉公式， 。 因此因此 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、，可以證明，如果它是平面圖，則應滿足則應滿足m2n4m2n4，但它并不，但它并不滿足。滿足。 因此因此K K3,33,3不是平面圖。不是平面圖。5959 3 3庫拉托斯基定理判別法庫拉托斯基定理判別法 定義定義6-216-21 如果兩個圖如果兩個圖G G1 1和和G G2 2是同構的，或者通是同構的，或者通過反復插入或刪除度為過反復插入或刪除度為2 2的結點，它們能變成同構的圖，的結點，它們能變成同構的圖，則稱則稱G G1 1和和G G2 2在度為在度為2 2的結點內同構。的結點內同構。6060 定理定理6-166-16 （庫拉托斯基定理）（庫拉托斯基定理） 一個圖是平面圖的充要條件是它不包含

33、在度為一個圖是平面圖的充要條件是它不包含在度為2 2的的結點內與結點內與K K5 5同構的子圖，也不包含在度為同構的子圖，也不包含在度為2 2的結點內與的結點內與K K3,33,3同構的子圖。同構的子圖。 解法一解法一 （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），），其中結點集其中結點集V V是一有限非空集合，邊集是一有限非空集合，邊集E E是是V V中不同元素的中不同元素的有序對偶的集合。有序對偶的集合。 例例1 1 設設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）中，若存在一）中，若存在一條從結點條從結點v vi i到結點到結點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路、開路、回路、真路和環路、開路、回路、真路和環 2 2可達、短程和距離可達、短程和距離66

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

38、1 1，得可達矩陣，得可達矩陣P P與前面結果相同與前面結果相同6868 4 4結點的度結點的度 結點結點v v的出度，記作的出度，記作degdeg+ +（v v）。）。 v v的入度，記作的入度，記作degdeg（v v）。）。 結點結點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是連通的或是連通的或弱連弱連通通的；如果對于任意兩個結點，至少有一個結點到另一的；如果對于任意兩個結點，至少有一個結點到另一個結點是可達的，則稱個結點是可達的，則稱G G是是單向連通單向連通的；如果對于任意兩的；如果對于任意兩個結點，兩者之間是相互可達的，則稱個結點，兩者之間是相互可達的，則稱G G是是強連通強連通的。的。 例例5 5 弱連通弱連通單向連通單向連通強連通強連通7070 6 6子圖、真子圖和生成子圖子圖、真子圖和生成子圖 例例6 6 7171 7 7同構同構 例例7 77272 三、與無向圖類似的性質三、與無向圖類似的性質 定理定理6-1

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

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

42、A. 1條；條；B. 3條；條；C. 無數條無數條 （ ） （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 一個不包含環的有向圖一個不包含環的有向圖G G，若它只，若它只有一個結點有一個結點v v0 0的入度為的入度為0 0，而其它所有結點的入度都等，而其它所有結點的入

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

44、集V V ，以及從，以及從v v出發的出發的所有有向路中的邊構成的邊集所有有向路中的邊構成的邊集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 在一有向樹中，若每一結點的出度在一有向樹中，若每一結點的出度都小于或等于都小于或等于m

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

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

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

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

50、=n0 0118383 定理定理6-216-21 設設T T是一棵二元樹，是一棵二元樹，n n0 0 表示樹葉結點數，表示樹葉結點數，n n2 2表示出度為表示出度為2 2的結點數，則的結點數，則n n0 0 = n= n2 2+1+1。 證明證明 設設T T的結點數為的結點數為n n ，邊數為，邊數為m m ，出度為，出度為1 1的的 結點數為結點數為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 完全二元樹有奇數個結點。完全二元樹有奇數個結點。 8484練習練習6-86-81計算非同構的有向樹的個數。計算非