离散数学树.ppt

第16章 树
离 散 数 学
本章说明
树是图论中重要内容之一。
本章所谈回路均指初级回路（圈）或简单回路，不含复杂回路（有重复边出现的回路）。
整理ppt
2
无向树及其性质

无向树——连通1，1，1，5
(2) 1，1，1，1，2，4
(3) 1，1，1，1，3，3
(4) 1，1，1，2，2，3
(5) 1，1，2，2，2，2
(4)对应两棵非同构的树，
在一棵树中两个2度顶点相邻，
在另一棵树中不相邻，
其他情况均能画出一棵非同构的树。
整理ppt
13

人们常称只有一个分支点，且分支点的度数为n-1的n(n≥3)阶无向树为星形图，称唯一的分支点为星心。
整理ppt
14

7阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。
解答 设Ti为满足要求的无向树，则边数mi＝6，于是
∑d(vj)＝12＝e+3+d(v4)+d(v5)+d(v6)。
由于d(vj)≠1∧d(vj)≠3，而且d(vj)≥1且d(vj)≤6，j＝4,5,6，
可知d(vj)＝2，j＝4,5,6。于是Ti 的度数列为
1，1，1，2，2，2，3
由度数列可知，Ti中有一个3度顶点vi，vi的邻域N(vi)中有3个顶点，这3个顶点的度数列只能为以下三种情况之一：
1,1,2 1,2,2 2,2,2
设它们对应的树分别为T1，T2，T3。此度数列只能产生这三棵非同构的7阶无向树。
整理ppt
15

整理ppt
16
例题
例题 已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。
解答 设有x片树叶，于是结点总数为
n＝1+2+x＝3+x
由握手定理和树的性质m＝n1可知，
2m＝2(n1)＝2×(2+x)
＝1×3+2×2+x
解出x＝3，故T有3片树叶。
故T的度数应为1、1、1、2、2、3。
整理ppt
17
例题 已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点的度数均为4，求T的阶数n，并画出满足要求的所有非同构的无向树。
解答 设T的阶数为n, 则边数为n1，4度顶点的个数为n7。
由握手定理得
2m = 2(n1) = 51+21+31+4(n7)
解出n = 8，所以4度顶点为1个。
故T的度数列为1、1、1、1、1、2、3、4。
例题
整理ppt
18
小节结束
例题
整理ppt
19
生成树
设G为无向图，
（1）T为G的树—T是G的子图并且是树。
（2）T为G的生成树—T是G的生成子图并且是树。
（3）e为T的树枝—设T是G的生成树，e∈E(G)，若e∈E(T)。
（4）e为T的弦—设T是G的生成树，e∈E(G)，若eE(T)。
（5）生成树T的余树—导出子图G[E(G)-E(T)] 。记作
整理ppt
20
注意： 不一定连通，也不一定不含回路。
说明
整理ppt
21
无向图G具有生成树当且仅当G连通。
证明 必要性，显然。
充分性（破圈法）。
若G中无回路，G为自己的生成树。
若G中含圈，任取一圈，随意地删除圈上的一条边，
若再有圈再删除圈上的一条边，直到最后无圈为止。
易知所得图无圈(当然无回路)、连通且为G的生成子图，
所以为G的生成树。
生成树的存在条件
整理ppt
22
最小生成树
设T是无向连通带权图G＝<V,E,W>的一棵生成树，
T的各边权之和称为T的权，记作W(T)。
G的所有生成树中权最小的生成树称为G的最小生成树。
求最小生成树的算法（避圈法(Kruskal)）
(1)设n阶无向连通带权图G＝<V,E,W>有m条边。不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大排序：e1,e2,…,em。
(2)取e1在T中。
(3)依次检查e2,…,em ，若ej(j≥2)与已在T中的边不构成回路，取ej也在T中，否则弃去ej。
(4)算法停止时得到的T为G的最小生成树为止。
整理ppt
23

求下图所示两个图中的最小生成树。
W(T1)＝6
W(T2)＝12
整理ppt
24
例题
例如 求所示图的一棵最小生成树。
解答
最小生成树 W(T)=38
小节结束
整理ppt
25
根树及其应用
设D是有向图，若D的基图是