树 无向树及其应用 生成树 根树及其应用.

Presentation on theme: "树 无向树及其应用 生成树 根树及其应用."— Presentation transcript:

1 树 无向树及其应用 生成树 根树及其应用

2 树 定义 16.1 连通无回路的无向图称为无向树，简称为树。每个连通分支都是树的无向图称为森林。平凡图称为平凡树。在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。 任何子图与圈同构则不是树

3 树的等价命题 设G=<V , E>是n阶m条边的无向图，则下面各命题等价： G是树； G中任意两个顶点之间存在唯一的路径；
定理 16.1 设G=<V , E>是n阶m条边的无向图，则下面各命题等价： G是树； G中任意两个顶点之间存在唯一的路径； G无回路且m=n-1； G连通且m=n-1； G连通且任何边都是桥； G无回路,但增加一边后得到且仅得一个圈； G连通且任何边都是桥 G中任意两个顶点之间存在唯一的路径 G无回路,但增加一边后得到且仅得一个圈 G无回路且m=n-1 G连通且m=n-1

4 树的等价命题 若G中存在回路，根据回路的长度分两种情况： 若G中的某个顶点v关联环，到自身存在长为0和1的两条路径；
n=1时，平凡图中不存在环，边数为0，结论成立。 设n=k时结论成立，即边数m=k-1。 当n=k+1时，删除G中任意一条边。由于G任意顶点间存在唯一路径，因此G将生成两个连通分支G1、G2。由于两个连通分支的顶点数n1、n2均小于等于k，因此边数m1、m2分别为n1 -1、 n2 -1，且有n1 + n2 =n=k+1。 因此G中边的数量为1+m1+ m2 =n-1=k。 除了最初的顶点之外，每增加一个定点就会增加一条边 G无回路且m=n-1 G连通且m=n-1

5 树的等价命题 由于G连通且任何边都是桥，因此对于任何两个顶点若删除顶点间路径上的一条边都会使两顶点属于不同连通分支，因此不存在回路。
设会形成一个以上的圈，则删除新边之后，新边关联的两个顶点之间存在两条不同的通路，其中存在边不是桥。 G无回路,但增加一边后得到且仅得一个圈 G无回路且m=n-1 G连通且m=n-1

6 最少树叶数 定理 16.2 设T是n阶非平凡的无向树,则T至少存在两片树叶。 1、顶点数确定则边数确定； 2、叶子顶点度为1；
根据定理16.1，n阶非平凡无向树的边数为n-1，度数为2n-2。 若叶子顶点为k个，则分支点数量为n-k个，且其度数均大于等于2。 因此T的度数至少为2(n-k)+k=2n-k。 若k小于2，则T的度数将大于2n-2，与定理16.1的结论矛盾。

7 例子 画出所有的6阶非同构无向树 树中仅包含5条边，且每个顶点的度至少为1。从完全图中依次选出5条边，并与已有生成图进行同构判断。
若采用邻接矩阵表示，则每行每列中至少有一个1，至多有5个1，对角线元素均为0，总共有10个元素为1，且矩阵为对称阵。 for(L1=1;L1<=5;L1++) { for(L2=1;L2<=5;L2++) … … for(L6=1;L6<=5;L6++) 条件检查；同构检查； }

8 生成树 定义 16.2 如果无向图G的生成子图T是树，则称T是G的生成树。设T是G的生成树，G的在T中的边称为T的树枝，不在T中的边称为T的弦。称T的所有弦的导出子图为T的余树，记为 余树可能存在回路 余树不一定连通

9 生成树存在的充要条件 定理 16.3 无向图G有生成树当且仅当G是连通图。 若G有生成树，显然各个顶点之间是连通的。必要性得证
推论 设G为n阶m条边的无向连通图，则m≥n-1。

10 生成树与弦 定理 16.4 设T为无向连通图G中一棵生成树，e为T的任意一条弦，则T∪e中含G中只含一条弦其余边均为树枝的圈，而且不同的弦对应的圈也不同。

11 基本回路 定义 16.3 设T是n阶m条边的无向连通图G的一棵生成树,设e’ 1 ，e’2，…，e’m-n+1为T的弦，Cr为T添加e’r产生的G中的圈，称Cr为G的对应弦e’r的基本回路或基本圈。称{C1, …, Cm-n+1}为G对应T的基本回路系统,称m-n+1为G的圈秩，记作ξ(G)。 不同的生成树对应的基本回路系统形态各异、数量相同。 zeta

12 树枝与割集 定理 16.5 设T是连通图G的一棵生成树，e为T的树枝，则G中存在只含树枝e，其余边都是弦的割集，且不同的树枝对应的割集也不同。

13 基本割集 定义 16.4 设T是n阶连通图G的一棵生成树,设e 1 ，e2，…，en-1为T的树枝，Si(i=1,2,.. ,n-1)是由树枝ei和弦构成的割集，则称Si是对应树枝ei的基本割集。称{S1,S2,…Sn-1}为G对应T的基本割集系统,称n-1为G的割集秩，记作η(G)。 不同的生成树对应的基本割集系统形态各异、数量相同。 eta

14 最小生成树 定义 16.5 设无向连通带权图G=<V , E , W>，T是G的一棵生成树，T的各边权之和称为T的权，记作W(T)。G的所有生成树中权最小的生成树称为G的最小生成树。 通信光缆的铺设

15 最小生成树的生成 1.在G(n,m)中选取权最小的边,记作e1,置i=1 2.当i=n-1时结束,否则转3。
3.设已选择边为e1,e2,……eI,此时无回路。 在G中除这i条边外,选择边ei+1,该边使得{e1,…,ei+1}生成的子图中无回路,并ei+1是满足该条件中权最小的一条边。 4.置i:=i+1,转2。 当克鲁斯卡尔是二年级研究生时，他发现了产生最小生成树的算法。他不能肯定他这个只有两页半的论文是否值得发表，但是被其他人说服而递交了它。 克鲁斯卡尔和罗伯特·普林在20世纪50年代中期提出他们的算法。不过，他们不是首先发现这些算法的人。例如，人类学家扬·切卡诺夫斯基在1909年的工作就包含了求最小生成树所需要的许多想法

16 最小生成树的生成 无需进行回路判断 1.在G(V , E , W)中选取一个顶点v,将其加入V1。
2.当V1包含G中所有顶点时结束,否则转3。 3.考察V-V1中所有顶点与V1中顶点之间的边，选择其中权最小的边对应的顶点加入V1，并保留相应的边。 4.置i:=i+1,转2。 无需进行回路判断

17 根树 定义 16.6 若有向图的基图是无向树，则称这个有向图为有向树。一个顶点的入度为0，其余顶点的入度为1的有向图称为根树。入度为0的顶点称为树根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点。内点和树根统称为分支点。从树根到任意顶点v的路径的长度称为v的层数。所有顶点的最大层数称为树高。

18 根树 定义 16.7 设T为一棵非平凡的根树，∀vi,vj∈V(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代；若vi邻接到vj，则称vi为vj的父亲，vj为vi的儿子。若vi, vj父亲相同，则称两顶点是兄弟。 二叉树 二叉正则树 二叉完全正则树 若T的每个分支点至多有r个儿子，则称T为r叉树；又若r叉树是有序的，则称它为r叉有序树。 若T的每个分支点恰好有r个儿子，则称T为r叉正则树；又若r叉树是有序的，则称它为r叉正则有序树。 若T是r叉正则树，且每个树叶的层数均为树高，则称T为r叉完全正则树，又若T是有序的，则称它为r叉完全正则有序树。

19 根子树及最优2叉树 定义 16.8 设T为一棵根树，∀v∈V(T)，称v及其后代的导出子图Tv为T的以v为根的根子树。
2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为该分支点的左子树和右子树。 定义 16.9 设2叉树T有t片树叶v1, v2, …, vt，权分别为w1, w2, …, wt，称 为T的权，其中l(vi)为vi的层数。在所有的t片树叶，带权w1, w2, …, wt的2叉树中，权最小的2叉树称为最优2叉树。

20 Huffman算法 给定实数w1, w2,…, wt，且w1≤w2≤…≤ wt 。
1）连接权为w1, w2的两片树叶，得一个分支点，其权为w1＋ w2。 2）在w1+w2, w3,…, wt中选两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权。 3）重复2）直到形成t－1个分支点，t片树叶为止。 尽量使权重小者远离树根

21 二元前缀码 定义 16.10 设α1α2,…,αn-1αn为长为n的符号串，称其子串α1, α1α2,…, α1α2,…,αn-1分别为该符号串的长度为1，2，…,n－1的前缀。设A={β1, β2,…, βm}为一个符号串集合，若对于A中任意的βi,βj,i≠j, βi,βj互不为前缀，则称A为前缀码。若符号串βi(i=1,2…m)中只出现0,1两个符号，则称A为二元前缀码。 1 00 011 0101 01001 01000 译码表 国家电话号码前缀 ISBN UTF-8 CDMA 编码流 直接译码,无回溯

22 二元前缀码例子 1 1 1 1 1 1 1 1 1

23 最佳前缀码 100 常用字句尽量简化 40 60 20 20 35 25 10 10 20 15 未必是唯一的形式 5 5 10 10 5
叶子节点上的权值就是使用频率;距离根节点越远则编码越长;子树上所有叶子节点引发的总的编码长度就是所有中间节点之和. 20 15 未必是唯一的形式 5 5 10 10

24

25 树的周游 递归思想 子树 二叉树的周游： 对一棵根树的每个顶点都访问一次且仅一次称为行遍或周游一棵树。
1）中（根）序行遍法：访问的次序为，左子树，树根，右子树。 2）前（根）序行遍法：访问的次序为，树根，左子树，右子树。 3）后（根）序行遍法：访问的次序为，左子树，右子树，树根。 子树 递归思想

26 语法树 * (a*(b+c)+d)*e e * e + d a b c ( ) 中序遍历：a*b+c+d*e 前序遍历：*+*a+bcde
嵌套调用 调用返回 中序遍历：a*b+c+d*e 前序遍历：*+*a+bcde 后序遍历：abc+*d+e* + d 中序遍历具有二义性 * ( a ) 嵌套调用 调用返回 + c b