离散数学课程论文

(4) 内点——入度为1，出度不为0的顶点 (5) 分支点——树根与内点的总称

(6) 顶点v的层数——从树根到v的通路长度 (7) 树高——T中层数最大顶点的层数 (8) 根树——平凡树也是根树 根树的画法

树叶——8片 内点—— 6个 分支点—— 7个 高度—— 5 家族树

常将根树看成家族树，家族中成员之间的关系如下定义。 定义16.7 设T为一棵非平凡的根树，

?vi、vj∈V(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代。 若vi邻接到vj（即∈E(T)），则称vi为vj的父亲，而vj为vi的儿子。 若vj、vk的父亲相同，则称vj与vk是兄弟。

根树的分类

(1)设T为根树，若将T中层数相同的顶点都标定次序，

则称T为有序树。

(2)分类：根据根树T中每个分支点儿子数以及是否有序

? r叉树——每个分支点至多有r个儿子

r叉有序树——r叉树是有序的

? r叉正则树——每个分支点恰有r个儿子

r叉正则有序树——r叉正则树是有序的

? r叉完全正则树——树叶层数均为树高的r叉正则树

r叉完全正则有序树——r叉完全正则树是有序的

根子树、左子树、右子树

定义16.8 设v为根树T中任意一顶点，称v及其后代的导出子图为以v为根的根子树。

2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为该分支点的左子树、右

子树。

2叉数最常用。

最优二叉树

为T的权，其中l(vi)是vi的层数，在所有有t片树叶、带权w1, w2, …, wt的2叉树中，权最小的2叉树称为最优2叉树。

给定一组数字，为每片树叶的权，如何求最优2叉树？ 求最优树的算法(Huffman算法)

给定实数w1, w2, …, wt，且w1≤w2 ≤ … ≤ wt。

①连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2。

② 在w1+w2, w3, …, wt中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新

定义16.9 设2叉树T有t片树叶v1, v2, …, vt，权分别为w1, w2, …, wt，称

分支点及所带的权。

③ 重复② ，直到形成t?1个分支点、t片树叶为止。

前缀码

(1)前缀码的定义

定义16.10 设?1?2…,?n-1?n是长度为n的符号串，

称其子串?1, ?1?2, …, ?1?2…?n?1 分别为该字符串的长度为1,2, …,n-1的前缀。 设A={?1, ?2, …, ?m}为一个符号串集合，若对于任意的?i, ?j?A，i?j，?i, ?j互不为前缀，

则称A为前缀码。

若?i(i=1,2,…,m)中只出现0与1两个符号，则称A为二元前缀码。

定理16.6 由一棵给定的2叉正则树，可以产生唯一的一个二元前缀码。 最佳前缀码：由最优2叉树产生的前缀码称为最佳前缀码 说明：

? 由于在每一步选择两个最小的权的选法不唯一。 ? 因为两个权对应的顶点所放左右位置不同。

画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权应该相等，即它们都应该是最优树。

（10）平面图

平面图的定义 定义17.1

? G可嵌入曲面S——如果图G能以这样的方式画在曲面S上，即除顶点处外无边相

交。

? G是可平面图或平面图——若G可嵌入平面。

? G的平面嵌入——画出的无边相交的平面图。 ? 非平面图——无平面嵌入的图。

定理17.1 设G??G，若G为平面图，则G?也是平面图。 定理17.2 设G??G，若G?为非平面图，则G也是非平面图。 推论Kn(n?5)和K3,n(n?3)都是非平面图。

定理17.3 若G为平面图，则在G中加平行边或环所得图还是平面图。 即平行边和环不影响图的平面性。

定理17.4 平面图G中所有面的次数之和等于边数m的两倍，即

定义17.3 若在简单平面图G中的任意两个不相邻的顶点之间加一条新边所得图为非平面图，则称G为极大平面图。 定理17.5 极大平面图是连通的。

定理17.6n(n?3)阶极大平面图中不可能有割点和桥。

定理17.7 设G为n(n?3) )阶简单连通的平面图，G为极大平面图当且仅当G的每个面的次数均为3。

定义17.4 若在非平面图G中任意删除一条边，所得图G?为平面图，则称G为极小非平面图。

定理17.8 对于任意的连通的平面图G，有

n-m+r=2

其中，n、m、r分别为G的顶点数、边数和面数。

定理17.10 设G为连通的平面图，且每个面的次数至少为l(l?3)，则 G的边数与顶点数有如下关系：