计算机数学树

毒酢:敌肓第25讲树

》本讲内容

1.无向树与生成树

2.有向树及其应用

,目的要求

口知道树、生成树、根树、树的遍历等概

念；知道根树的分类

□会用避圈法和破圈法求带权无向连通图

的最小生成树

□掌握二元有序正则树的应用

2011-1-21第25讲树周忠荣编1

毒酢:敌肓1.无向树与生成树

口补充实例下左图给出了一次乒乓球男子

单打比赛半决赛和决赛的进程。下右图

表明，在半决赛中刘国梁胜了马林，王

涛胜了孔令辉。决赛中王涛战胜刘国梁

夺得冠军。

2011-1-21第25讲树周忠荣编2

毒酢:敌肓1.（续一）

।口定义7・18不含回路的连通三向图称为无

向树，简称树，通常用律示。

树中度数为1的结点称为树叶，度数大于

1的结点称为分支点。树中的边称为树枝。

i连通分枝数大于1且每个连通分枝均是树

的非连通图称为森林。

2011-1-21第25讲树周忠荣编3

毒酢:敌肓1.(续二)

□定理7-6设G是含有〃个结点、m条边的

简单无向图，则下列命题等价：

(1)G是树；

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

(3)G中任意两结点间有惟一的简单路径;

(4)G连通，且去掉任意一条边就不再连

通；

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

2011-1-21第25讲树周忠荣编4

毒酢:敌肓1.(续三)

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

(7)G中无回路，但在任意两个不邻接结

点加一条边就形成一个回路。

□定义6・19设弓=〈，声〉是无向连通图，

7是G的生成子图，并且7是树，则称T是

G的生成树，G的不在T中的边称为雁］弦。

2011-1-21第25讲树周忠荣编5

毒酢:敌肓1.（续四）

□定理7-7设G=<“〉是无向连通图,

则G至少有一棵生成树。

2011-1-21第25讲树周忠荣编6

毒酢:敌肓1.（续五）

I□推论设碇含有几个结点、加条边的简单

先向连通囱，则相,r一1。

口破圈法

口例7・17画出下图所示的简单无向图的3

个生成树。

2011-1-21第25讲树周忠荣编7

毒酢:敌肓1.（续六）

□解

(a)

2011-1-21第25讲树周忠荣编8

毒酢:敌肓1.(续七)

□定义7-20设6=〈V0是带权无向连通

图，则G中具有最小权的生成树称为G的

最小生成树。

□避圈法步骤:

口(1)在图G中选取权最小的一条边(如

果存在多个权最小的边，任选其中一

个)，并记该边连同其两个端点为图4

□(2)在图G中与图Z邻接的所有边中找

权最小的一条边，把它连同其端点添加

到图4币。

2011-1-21第25讲树周忠荣编9

毒酢:敌肓1.（续八）

□（3）重复第（2）步，但要在保证图Z

不出现回路的前提下找权最小的一条边,

直至包含了图G中是所有结点。

口求最小生成树的破圈法本质上与求生成

树的避圈法一样，只是要尽可能去掉权

大的边。

□Kruskal算法

2011-1-21第25讲树周忠荣编10

毒酢:敌肓1.（续九）

□例7・18下图是一个局域网的示意图。问

选择怎样的线路使敷设的网络线总长最

2011-1-21第25讲树周忠荣编11

毒酢:敌肓1.（续十）

□避圈法求解

2011-1-21第25讲树周忠荣编12

毒酢:敌肓1.（续十一）

2011-1-21第25讲树周忠荣编13

毒酢:敌肓1.（续十二）

□下列命题是否成立?

A.含有5根树枝的树只能有4个结点。

B.含有5根树枝的树只能有6个结点。

C.含有5个结点的树只能有6根树枝。

D.含有5个结点的树只能有4根树枝。

E.树的任意两个结点间都有路径。

2011-1-21第25讲树周忠荣编14

毒酢:敌肓1.（续十三）

F.树的任意两个结点间都只有一条路

径。

G.在树的任意两个不邻接的结点间添

加一条边所得的图仅有一条回路。

H.从树中删除任意一条边后所得的图

就不再连通。

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

J.任何图都有生成树。

2011-1-21第25讲树周忠荣编15

毒酢:敌肓1.（续十四）

口补充例题1画出下图所示的简单无向图

的3个生成树。

2011-1-21第25讲树周忠荣编16

ri.（续十五）

口补充例题2求下面带权图的的最小生成

树。

2011-1-21第25讲树周忠荣编17

毒酢:敌肓1.（续十六）

□用破圈法

2011-1-21第25讲树周忠荣编18

号片2.有向树及其应用

□定义7・21如果一个有向图在不考虑边的

方向时是树，则称此有向图为有向树，

简称树。

□定义7・22一棵有向树，如果仅有一个结

j点的入度为0,其余结点的入度均为1,

则称此有向树为根树。入度为0的结点称

为树根，出度为0的结点称为树叶，出度

不为0的结点称为分枝点。

2011-1-21第25讲树周忠荣编19

，旧2.有向树及其应用(续一)

口左边的图不是根树

□右边的图是根树树根

这个点的这个点的只有这个点

入度为0入度也为0的入度为0

树叶分枝点

(b)

2011-1-21第25讲树周忠荣编20

，旧2.有向树及其应用（续二）

□根树的简便画法。

2011-1-21第25讲树周忠荣编21

暂看2.有向树及其应用（续三）

□层数同一层树高

2011-1-21第25讲树周忠荣编22

，旧2.有向树及其应用（续四）

□家族树儿子父亲兄弟后代祖

先

口定义7-23根子树

2011-1-21第25讲树周忠荣编23

，旧2.有向树及其应用（续五）

□定义7・25〃元树〃元正则树〃元有

序树〃元完全正则树〃元完全正则树

〃元有序完全正则树

2元完全正则树

2011-1-21第25讲树周忠荣编24

，旧2.有向树及其应用（续六）

□例7-19下图中的几个根树各属于哪

一类？

2011-1-21第25讲树周忠荣编25

号片2.有向树及其应用(续七)

।□对于根树中的每个结点都只访问一次称

为可遍历或周游一棵树，对于二元有序

正则树主要有以下3种遍历方法。

(1)中序遍历法其访问次序为：左子树、

树根、右子树。

⑵前序遍历法其访问次序为：树根、左

子树、右子树。

⑶后序遍历法其访问次序为：左子树、

右子树、树根C

2011-1-21第25讲树周忠荣编26

号片2.有向树及其应用(续八)

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

后根据不同的遍历法可以产生不同的算

法。

口用二元有序树表达算式时必须符合下面

।的规定：

⑴运算符必须放在分枝点上；

(2)数字或表示数值的字母放在树叶上；

(3)被减数或被除数左枝树树叶上。

2011-1-21第25讲树周忠荣编27

，旧2.有向树及其应用（续九）

口按不同的遍历法访问右图所示的根

树结果不同。

□按中序遍历法访问的结果是：

(db(hei))a(fcg)

2011-1-21第25讲树周忠荣编28

，旧2.有向树及其应用（续十）

□按先序遍历法访问的结果是：

a(bd(ehi))(cfg)

按后序遍历法访问的结果是:

(d(hie)b)[fgc)a

h

2011-1-21第25讲树周忠荣编29

2011-1-21第25讲树周忠荣编30

毒酢:敌肓本讲小结

口无向树、生成树、最小生成树、有向树、

根树等概念要准确理解。

口用避圈法求连通图的最小生成树要注意

两点：（1）尽可能选择当前图中权最小的

边；（2）保证得到的图不能有回路。

2011-1-21第25讲树周忠荣编31

毒酢: