树及树的应用文档格式.docx
- 文档编号:3699064
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:12
- 大小:140.97KB
树及树的应用文档格式.docx
《树及树的应用文档格式.docx》由会员分享,可在线阅读,更多相关《树及树的应用文档格式.docx(12页珍藏版)》请在冰点文库上搜索。
在图1.1中(a)所示是树,因为它连通又不含回路。
但1.1(b)所示不是树,因为图1.1(b)虽然连通但有回路。
图1.1(c)虽无回路但不连通。
在树中,次数为1的结点称为叶(悬挂点)。
如图1.1(a)中,V1、V4、V5等均为叶。
在树中,次数大于1的结点称为分枝点。
如图1.1(a)中,V2、V3均为分枝点。
仅有一个结点称为平凡树。
1.2无向树的性质
定理1.2.1在(n,m)树中必有m=n-1
[证]用数学归纳法对n进行归纳
n等于1时定理成立
设对所有i(i<
n)定理成立,需求证在n时有m=n-1
设有一(n,m)树,由于其不包含任何回路,故从树中删去一边后就变成两个互不连通的子图。
而其每个子图是连通的,故其每个子图均为树。
设它们分别是(n1,m1)树及(n2,m2)树,由于n1<n,n2<n。
故有归纳假设可得,
m1=n1-1,m1=n1-1
又因为
n=n1+n1,m2=n2-1
故得到m=n-1
定理1.2.2非平凡树至少有两片叶子
[证]设树T=〈V,E〉,│V│=v,因为T是连通图,对于任何vi 属于T有deg(vi)<
1且∑deg(vi)不大于2v得出矛盾。
若T中只有一个结点度数为1,其它结点度数大于等于2,则
∑deg(vi)≤2v-1
得出矛盾。
故T中至少有两个结点度数为1。
定理1.2.3(n,m)无向图构成树↔每对结点的通路只有一条
[证]必要性:
若有图G是树,故每对节点间均有通路。
若结点vi与vj间有两条通路,则此两条通路必构成一条回路,而这与树的定义矛盾。
充分性:
图G的每对结点间存在通路,故G是连通的。
又由于通路的唯一性,故知图中不包含回路,由此可知G是树。
1.3特殊的无向树(生成树)
1.3.1生成树的有关定义及其性质
定义1.3.1设有无向图G的生成子图构成树,则称其为生成树。
由一个连通图找它的生成树的过程是:
方法一:
破圈法。
设G是一个连通图,如果G是树,则G本身就是G的生成树。
如果G不是树,则G至少有一个回路c,在c中任取一条边e,则G-e仍是连通图。
即G1=G-e是G的连通生成子图。
如果G1仍不是树,可以继续这个过程,直到一条边从最后一个回路中去掉。
所得图T就是G的一个连通生成子图,而且没有回路,故T就是G的生成树。
方法二:
避圈法。
设G是一个连通图。
在V(G)中逐次添加E(G)中的边,要求每次添加边后所得子图都不含回路。
把上述过程进行到无法再进行为止。
所得到的子图T是G的一个极大无回路生成子图,T就是G的生成树。
定理1.3.1连通图至少有一颗生成树。
[证]设连通图G没有回路则G本身就是一棵生成树。
若G至少有一个回路,我们删去G的回路上的一条边,得到图G1就是生成树。
若G1仍有回路,再删去G1回路上的一条边。
重复上述步骤,直至得到一个连通图H,它没有回路。
但与G有同样的结点集,因此H是 G生成树。
由此定理得证。
1.3.2最小生成树
定义1.3.2在图G的所有生成树中,树权最小的那棵生成树称作最小生成树。
其中树权记作T(w)。
用避圈法找最小生成树。
将图中的环去掉。
将图中个边的权按从小到大的顺序排列w1,w2… wn( l1,l2…lm )。
先取l1,看l2 …lm与l1是否构成回路,构成回路的删去,不构成的留下。
继续以上方法,最后得到的生成树为最小生成树。
如图1.3.2中实线组成的图形为最小生成树。
2有向树的有关概念
2.1有向树的有关定义
定义2.1.1在有向图中不考虑边的方向而构成树,则称此有向图为有向树。
例如图2.1(a)所绘出的有向图即为有向树,但图2.1(b)所绘出的有向图则不是有向树,因为当忽略其方向时该图存在回路。
定义2.1.2若一颗有向树恰有一个结点的引入次数为0,其余所有节点的引入次数为1,则称该有向树为树形图。
例如图2.1.2中(a),(b)所示是树形图。
在树形图中引入次数为零的结点称为树形图的根。
如图2.1.2(a)中V1。
引入次数为1,引出次数为0的结点称为树形图的叶。
如图2.1.2(a)中v2,v4,v6。
引入次数为1,引出次数非零的结点称为树形图的内点。
如图2.1.2(a)中v3,v5
2.2特殊有向树
定义2.2.1有且仅有一个结点的引入次数为0,其它结点的引入次数为1,还有一些结点的引出次数为0的有向树称为外向树(根树)。
例如图2.1.2中(a),(b)所示是外向树。
定义2.2.2有且仅有一个结点的引出次数为0,其它结点的引出次数为1,还有一些结点的引出次数为0的有向树称为内向树。
例如图2.2.2所示
3根树(外向树)
定义3.1在树形图中有且仅有一个引入次数为零的结点称为根。
定义3.2根到结点vi的层数称为该结点vi的层数。
定义3.3外向树的最大层数称为树高。
例如图3.0所给出的图是根树。
在图3.0中,v0是根。
v5,v6,v7,v8,v9是树叶。
v1,v2,v3,v4是内点。
v0,v1,v2,v3,v4统称为分枝点。
结点v0的层数为0。
结点v1,v2的层数为1,结点v3,v4,v5的层数为2。
结点v6,v7,v8,v9的层数为3。
这样的树形图的高为3。
4二元树
外向树除叶外每个节点的引出次数均大于0。
结点的引出次数均不超过某一正整数m,则称此外向树为m元树。
由此可以定义m元树如下:
定义4.1n个结点的外向树如满足:
引出次数deg(vi)≤m(i=1,2…n)
则称此外向树为m元树。
如满足(除叶外):
引出次数deg(vi)=m(i=1,2…n)
则称此外向树为m元完全树。
定理4.1设有m元完全树,其树叶树为t,分枝点数为i,则(m-1)×
i=t-1
[证]若把m元树看做是每局有m位选手参加比赛的单淘汰撒计划表。
树叶数t表示参加比赛的选手数。
分枝点数i表示比赛的局数。
因为每局比赛将淘汰(m-1)位选手,故比赛结果共淘汰(m-1)×
i位选手,最后剩下一位冠军。
因此(m-1)×
i=t-1。
定义4.2设有有权树D=〈V,E,w〉。
w1,w2…wn为叶的权。
T(w)=∑wi×
l(vi)中最小的2元树称为最优2元树。
画出最优2元树的步骤如下:
1 将叶的权从小到大排列w1,w2…wn。
2 将权为w1,w2的两片叶子画出,引出新的结点的权数为w1+w2。
3 权为w1+w2与w3…wn的比较画出结点。
继续上述过程得到的2元树为最优2元树。
图4.0(a)(b)(c)(d)分别绘出了四元树、四元完全树、二元树、二元完全树的例子。
在二元树中每个节点最多可以有两个儿子,一般称位于左边的为做儿子,右边的为右儿子。
二元树是一种比较重要的外向树,好多实际问题均可用二元树表示。
下面举几个这方面的例子。
例可用二元树表示算术表达式,如下列表达式
(v1-v2)/v3+v4(v5-v6/v7)
这个表达式可用图4.1所示有序二元树表示。
例很多计算机中的程序流程图可用有序二元树表示。
如图4.2(a)所示的流程图及可用图4.2(b)的有序二元树表示。
5树的应用
例1有十个学生参加一次考试,试题10道。
已知没有两个学生作对的题目是相同的。
证明:
在这10道题中可以找到一道试题,将这道试题取消后,每两个学生所做对的题目仍然不会相同。
反证法。
用10个结点vi(i=1,2…10)来表示10位学生。
如果结论不成立,则对每一道试题h(1≤h≤10),如果去掉h,比有两个学生vi和vj,他们作对的题目是完全相同的,即原来vi比vj或vj比vi恰好多做一题h,就在vi和vj之间连一条边,并标上号h(如果有好几对,我们可以任取一对)。
这样就得到一个具有10个结点,10条边的简单图,用G表示。
有定理可知,G不是树。
因为结点数与边数相同。
G含有回路,设为
C=vi1vi2…vikvi1
则沿着C走时,每通过一条边就相当于解出的题目增加或减少了一道题,并且增减的题目是互不相同的。
现在对回路C来说。
从vi1出发沿C走一圈回到vi1,就相当于vi1做对的题目会增加一些,在减少一些题目,最后结果仍是vi1原来做对的题目,这是一个矛盾。
例2用树形图可以表示家庭之间的关系。
设某祖宗A有两个儿子B、C,B与C分别有三个儿子D、E、F及G、H、I,而D与G分别又有一个儿子J及K。
这样的家庭关系可以用如下树形图5.2表示。
例3设有28盏灯,拟共用一个电源插座.问需用多少块具有四插座的插线板.
解:
将四叉树的每个分枝点看作是具有四插座的接线板,树也看作是电灯,则有(4-1)×
i=28-1,i=9,所以需要九块具有四插座的接线板。
例4假设有一台计算机,它有一条加法指令,可计算三个树的和。
如果要计算九个数的和,至少要执行几次家发指令。
若把这就个数看作是完全三叉树的九片叶子,则有(3-1)×
i=9-1,i=4。
所以需要之心四次加法指令。
例5如图5(a)中给出了一个连通图,求此图的生成树。
求图5(a)的生成树过程可用图5(b)到图5(e)表示。
例6绘出公式(P∨(¬
P∧Q))∧((¬
P∨Q)∧¬
R)的根树表示。
例7在一棵有2个结点,次数为2。
4个结点次数为3。
其余结点都是叶的无向树中,共有几片叶子。
设X为其余结点。
其中n=2+4+X,m=n-1=X+5。
由握手定理与结点和边的关系2×
2+4×
3+X×
1=2×
(X+5)。
解得X=6。
例8构造带权3、4、7、8、10、12的最优二元树。
这样的最优二元树的权为
w(T)=3×
4+4×
4+7×
3+8×
2+10×
2+12×
2=109
构造过程如图5.8所示。
参考文献:
1.卜月华著,《图论及其应用》,南京:
东南大学出版社,2000。
2.左孝凌等著,《离散数学》,上海:
上海科学技术文献出版社,2001。
3.徐洁磬著,《离散数学导论》,北京:
高等教育出版社,2007。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用