第10章树(10.5).ppt

10.2 树 10.2.1 树的定义与性质 树的特点 在结点给定的无向图中， 树是边数最多的无回路图 树是边数最少的连通图 由此可知，在无向图G = (n, m)中， 若m＜n-1，则G是不连通的 若m＞n-1，则G必含回路 定理10.2.2 任意非平凡树T = (n, m) 都至少有两片叶。 10.2.2 生成树 定义10.2.2 给定图G = V, E，若G的某个生成子图是树，则称之为G的生成树，记为TG。生成树TG中的边称为树枝；G中不在TG中的边称为弦；TG的所有弦的集合称为生成树的补。 定理10.2.3 图G = V, E存在生成树TG = V, ET的充分必要条件是G是连通的。 求生成树的破圈法与避圈法 算法10.2.1 求连通图G = n, m的生成树的破圈法： 每次删除回路中的一条边，其删除的边的总数为m-n+1。 算法10.2.2 求连通图G = n, m的生成树的避圈法： 每次选取G中一条与已选取的边不构成回路的边，选取的边的总数为n-1。 注：生成树不是惟一的。 例10.2.4 分别用破圈法和避圈法求下图的生成树。 避圈法 因生成树不惟一，故上述两棵生成树都是所求的。 破圈法和避圈法的计算量较大，主要是需要找出回路或验证不存在回路。还有一种广度优先有哪些信誉好的足球投注网站算法： 10.2.3 最小生成树 定义10.2.3 设G = V, E是连通的赋权图，T是G的一棵生成树，T的每个树枝所赋权值之和称为T的权，记为w(T)。G中具有最小权的生成树称为G的最小生成树。 算法10.2.3 Kruskal算法 （1）在G中选取最小权边e1，置i = 1。 （2）当i = n-1时，结束，否则转(3)。 （3）设已选取的边为e1, e2, …, ei，在G中选取不同于e1, e2, …, ei的边ei+1，使{e1, e2, …, ei, ei+1}中无回路且ei+1是满足此条件的最小权边。 （4）置i = i+1，转(2)。 例10.2.6 用Kruskal算法求图中赋权图的最小生成树。 10.3 根树 10.3.1 根树的定义与分类 定义10.3.1 一个有向图，若略去所有有向边的方向所得到的无向图是一棵树，则这个有向图称为有向树(Directed Tree)。 例10.3.1 判断下图中的图哪些是有向树？为什么？ 定义10.3.2 一棵非平凡的有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称之为根树或外向树。 入度为0的结点称为根；出度为0的结点称为叶；入度为1，出度大于0的结点称为内点；又将内点和根统称为分支点。 根树中，从根到任一结点v的通路长度，称为该结点的层数；称层数相同的结点在同一层上；所有结点的层数中最大的称为根树的高。 例10.3.2 判断下图所示的图是否是根树？若是根树，给出其根、叶和内点，计算所有结点所在的层数和高。 家族关系 定义10.3.3 在根树中，若从结点vi到vj可达，则称vi是vj的祖先(Ancestor)，vj是vi的后代(Descendant)；又若vi, vj是根树中的有向边，则称vi是vj的父亲(Father)，vj是vi的儿子(Son)；如果两个结点是同一个结点的儿子，则称这两个结点是兄弟(Brother)。 定义10.3.4 如果在根树中规定了每一层上结点的次序，这样的根树称为有序树(Ordered Tree)。 一般地，在有序树中同一层中结点的次序为从左至右。有时也可以用边的次序来代替结点的次序。 定义10.3.5 在根树T中， 若每个分支点至多有k个儿子，则称T为k元树(k-ary Tree)； 若每个分支点都恰有k个儿子，则称T为k元完全树(k-ary Complete Tree)； 若k元树T是有序的，则称T为k元有序树(k-ary Ordered Tree)； 若k元完全树T是有序的，则称T为k元有序完全树(k-ary Ordered Complete Tree)。 子树 在根树T中，任一结点v及其所有后代导出的子图T’称为T的以v为根的子树(Subtree)。 当然，T’也可以有自己的子树。 二元有序树的每个结点v至多有两个儿子，分别称为v的左儿子(Left Son)和右儿子(Right Son)。 二元有序树的每个结点v至多有两棵子树，分别称为v的左子树(Left Subtree)和右子树(Right Subtree)。 例10.3.3 判断下图所示的几棵根树是什么树？ k元完全树中分支点与叶结点数目之间的关系 定理10.3.1 在k元完全树中，若叶数为t，分支点数为i，则下式成立： (k-1)×i = t-1