計(jì)算機(jī)數(shù)學(xué)樹

毒酢:敵肓第25講樹

》本講內(nèi)容

1.無向樹與生成樹

2.有向樹及其應(yīng)用

,目的要求

口知道樹、生成樹、根樹、樹的遍歷等概

念；知道根樹的分類

□會(huì)用避圈法和破圈法求帶權(quán)無向連通圖

的最小生成樹

□掌握二元有序正則樹的應(yīng)用

2011-1-21第25講樹周忠榮編1

毒酢:敵肓1.無向樹與生成樹

口補(bǔ)充實(shí)例下左圖給出了一次乒乓球男子

單打比賽半決賽和決賽的進(jìn)程。下右圖

表明，在半決賽中劉國梁勝了馬林，王

濤勝了孔令輝。決賽中王濤戰(zhàn)勝劉國梁

奪得冠軍。

2011-1-21第25講樹周忠榮編2

毒酢:敵肓1.（續(xù)一）

?口定義7?18不含回路的連通三向圖稱為無

向樹，簡稱樹，通常用律示。

樹中度數(shù)為1的結(jié)點(diǎn)稱為樹葉，度數(shù)大于

1的結(jié)點(diǎn)稱為分支點(diǎn)。樹中的邊稱為樹枝。

i連通分枝數(shù)大于1且每個(gè)連通分枝均是樹

的非連通圖稱為森林。

2011-1-21第25講樹周忠榮編3

毒酢:敵肓1.(續(xù)二)

□定理7-6設(shè)G是含有〃個(gè)結(jié)點(diǎn)、m條邊的

簡單無向圖，則下列命題等價(jià)：

(1)G是樹；

(2)G連通且不含回路；

(3)G中任意兩結(jié)點(diǎn)間有惟一的簡單路徑;

(4)G連通，且去掉任意一條邊就不再連

通；

(5)G連通，S.n=m+1;

2011-1-21第25講樹周忠榮編4

毒酢:敵肓1.(續(xù)三)

(6)G中無回路,且〃=m+l;

(7)G中無回路，但在任意兩個(gè)不鄰接結(jié)

點(diǎn)加一條邊就形成一個(gè)回路。

□定義6?19設(shè)弓=〈，聲〉是無向連通圖，

7是G的生成子圖，并且7是樹，則稱T是

G的生成樹，G的不在T中的邊稱為雁］弦。

2011-1-21第25講樹周忠榮編5

毒酢:敵肓1.（續(xù)四）

□定理7-7設(shè)G=<“〉是無向連通圖,

則G至少有一棵生成樹。

2011-1-21第25講樹周忠榮編6

毒酢:敵肓1.（續(xù)五）

I□推論設(shè)碇含有幾個(gè)結(jié)點(diǎn)、加條邊的簡單

先向連通囪，則相,r一1。

口破圈法

口例7?17畫出下圖所示的簡單無向圖的3

個(gè)生成樹。

2011-1-21第25講樹周忠榮編7

毒酢:敵肓1.（續(xù)六）

□解

(a)

2011-1-21第25講樹周忠榮編8

毒酢:敵肓1.(續(xù)七)

□定義7-20設(shè)6=〈V0是帶權(quán)無向連通

圖，則G中具有最小權(quán)的生成樹稱為G的

最小生成樹。

□避圈法步驟:

口(1)在圖G中選取權(quán)最小的一條邊(如

果存在多個(gè)權(quán)最小的邊，任選其中一

個(gè))，并記該邊連同其兩個(gè)端點(diǎn)為圖4

□(2)在圖G中與圖Z鄰接的所有邊中找

權(quán)最小的一條邊，把它連同其端點(diǎn)添加

到圖4幣。

2011-1-21第25講樹周忠榮編9

毒酢:敵肓1.（續(xù)八）

□（3）重復(fù)第（2）步，但要在保證圖Z

不出現(xiàn)回路的前提下找權(quán)最小的一條邊,

直至包含了圖G中是所有結(jié)點(diǎn)。

口求最小生成樹的破圈法本質(zhì)上與求生成

樹的避圈法一樣，只是要盡可能去掉權(quán)

大的邊。

□Kruskal算法

2011-1-21第25講樹周忠榮編10

毒酢:敵肓1.（續(xù)九）

□例7?18下圖是一個(gè)局域網(wǎng)的示意圖。問

選擇怎樣的線路使敷設(shè)的網(wǎng)絡(luò)線總長最

2011-1-21第25講樹周忠榮編11

毒酢:敵肓1.（續(xù)十）

□避圈法求解

2011-1-21第25講樹周忠榮編12

毒酢:敵肓1.（續(xù)十一）

2011-1-21第25講樹周忠榮編13

毒酢:敵肓1.（續(xù)十二）

□下列命題是否成立?

A.含有5根樹枝的樹只能有4個(gè)結(jié)點(diǎn)。

B.含有5根樹枝的樹只能有6個(gè)結(jié)點(diǎn)。

C.含有5個(gè)結(jié)點(diǎn)的樹只能有6根樹枝。

D.含有5個(gè)結(jié)點(diǎn)的樹只能有4根樹枝。

E.樹的任意兩個(gè)結(jié)點(diǎn)間都有路徑。

2011-1-21第25講樹周忠榮編14

毒酢:敵肓1.（續(xù)十三）

F.樹的任意兩個(gè)結(jié)點(diǎn)間都只有一條路

徑。

G.在樹的任意兩個(gè)不鄰接的結(jié)點(diǎn)間添

加一條邊所得的圖僅有一條回路。

H.從樹中刪除任意一條邊后所得的圖

就不再連通。

I.任何圖都有生成子圖。

J.任何圖都有生成樹。

2011-1-21第25講樹周忠榮編15

毒酢:敵肓1.（續(xù)十四）

口補(bǔ)充例題1畫出下圖所示的簡單無向圖

的3個(gè)生成樹。

2011-1-21第25講樹周忠榮編16

ri.（續(xù)十五）

口補(bǔ)充例題2求下面帶權(quán)圖的的最小生成

樹。

2011-1-21第25講樹周忠榮編17

毒酢:敵肓1.（續(xù)十六）

□用破圈法

2011-1-21第25講樹周忠榮編18

號(hào)片2.有向樹及其應(yīng)用

□定義7?21如果一個(gè)有向圖在不考慮邊的

方向時(shí)是樹，則稱此有向圖為有向樹，

簡稱樹。

□定義7?22一棵有向樹，如果僅有一個(gè)結(jié)

j點(diǎn)的入度為0,其余結(jié)點(diǎn)的入度均為1,

則稱此有向樹為根樹。入度為0的結(jié)點(diǎn)稱

為樹根，出度為0的結(jié)點(diǎn)稱為樹葉，出度

不為0的結(jié)點(diǎn)稱為分枝點(diǎn)。

2011-1-21第25講樹周忠榮編19

，舊2.有向樹及其應(yīng)用(續(xù)一)

口左邊的圖不是根樹

□右邊的圖是根樹樹根

這個(gè)點(diǎn)的這個(gè)點(diǎn)的只有這個(gè)點(diǎn)

入度為0入度也為0的入度為0

樹葉分枝點(diǎn)

(b)

2011-1-21第25講樹周忠榮編20

，舊2.有向樹及其應(yīng)用（續(xù)二）

□根樹的簡便畫法。

2011-1-21第25講樹周忠榮編21

暫看2.有向樹及其應(yīng)用（續(xù)三）

□層數(shù)同一層樹高

2011-1-21第25講樹周忠榮編22

，舊2.有向樹及其應(yīng)用（續(xù)四）

□家族樹兒子父親兄弟后代祖

先

口定義7-23根子樹

2011-1-21第25講樹周忠榮編23

，舊2.有向樹及其應(yīng)用（續(xù)五）

□定義7?25〃元樹〃元正則樹〃元有

序樹〃元完全正則樹〃元完全正則樹

〃元有序完全正則樹

2元完全正則樹

2011-1-21第25講樹周忠榮編24

，舊2.有向樹及其應(yīng)用（續(xù)六）

□例7-19下圖中的幾個(gè)根樹各屬于哪

一類？

2011-1-21第25講樹周忠榮編25

號(hào)片2.有向樹及其應(yīng)用(續(xù)七)

?□對(duì)于根樹中的每個(gè)結(jié)點(diǎn)都只訪問一次稱

為可遍歷或周游一棵樹，對(duì)于二元有序

正則樹主要有以下3種遍歷方法。

(1)中序遍歷法其訪問次序?yàn)椋鹤笞訕洹?/p>

樹根、右子樹。

⑵前序遍歷法其訪問次序?yàn)椋簶涓?、?/p>

子樹、右子樹。

⑶后序遍歷法其訪問次序?yàn)椋鹤笞訕洹?/p>

右子樹、樹根C

2011-1-21第25講樹周忠榮編26

號(hào)片2.有向樹及其應(yīng)用(續(xù)八)

I□利用二元有序樹可以表示各種算式，然

后根據(jù)不同的遍歷法可以產(chǎn)生不同的算

法。

口用二元有序樹表達(dá)算式時(shí)必須符合下面

?的規(guī)定：

⑴運(yùn)算符必須放在分枝點(diǎn)上；

(2)數(shù)字或表示數(shù)值的字母放在樹葉上；

(3)被減數(shù)或被除數(shù)左枝樹樹葉上。

2011-1-21第25講樹周忠榮編27

，舊2.有向樹及其應(yīng)用（續(xù)九）

口按不同的遍歷法訪問右圖所示的根

樹結(jié)果不同。

□按中序遍歷法訪問的結(jié)果是：

(db(hei))a(fcg)

2011-1-21第25講樹周忠榮編28

，舊2.有向樹及其應(yīng)用（續(xù)十）

□按先序遍歷法訪問的結(jié)果是：

a(bd(ehi))(cfg)

按后序遍歷法訪問的結(jié)果是:

(d(hie)b)[fgc)a

h

2011-1-21第25講樹周忠榮編29

2011-1-21第25講樹周忠榮編30

毒酢:敵肓本講小結(jié)

口無向樹、生成樹、最小生成樹、有向樹、

根樹等概念要準(zhǔn)確理解。

口用避圈法求連通圖的最小生成樹要注意

兩點(diǎn)：（1）盡可能選擇當(dāng)前圖中權(quán)最小的

邊；（2）保證得到的圖不能有回路。

2011-1-21第25講樹周忠榮編31

毒酢: