chap14有向图题库.pptVIP

* 离散数学 * 有向树 定义14.3.1：若有向图T的基础图是树，则称T是有向树。 下面是两棵有向树，请注意它们的不同： * 离散数学 * 根树 定义14.3.2：设T是一个有向树，如果T中恰有一个顶点的入度为0，其它顶点的入度均为1，则称T为根树。根树T中入度为0的顶点称为T的根，记为vr或v0；根树中出度为0的顶点称为叶；根树中出度不为0的顶点称为分枝点。 注意：根树是一种特殊的有向树，并非所有的有向树都是根树。《图论》中“树”的概念要比《数据结构》中的“树”的概念广泛的多。《数据结构》中的“树”仅仅是这里的根树。 * 离散数学 * 根树的表示 对根树，我们一般将根画在最上面，即根在第0层，其它顶点u按根到u的唯一有向通路的长度由上至下依次画出，即将长度为i的顶点画在第i层。并规定弧的方向一律朝下，于是箭头可以省略不画； 树的高度：从根出发最长的有向通路之长称为T的高度。 * 离散数学 * 子树 T是一个树，v是T的一个分枝结点，由以v以及T中从v出发可达到的所有顶点连同所经过的弧构成以v为根的T的一个子树. 右边树中红色的部分是不是一个子树呢？ 注意：右边树中红色的部分不是一个子树！ * 离散数学 * 根树中的术语及其示例 T的高度为3 ; v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 T: v2为v6 , v7 , v8的 父结点 ; v6 , v7 , v8为v2的 子结点 ; v4 , v5 互为 兄弟结点 ; v9 , v10为v0 , v2的 后裔 ; v0 , v2 为v9 , v10的 祖先 ; T中的蓝色结点及弧构成 T的一个以v2为根的子树. * 离散数学 * 有序树 定义14.3.3：若对一个树T的结点(弧)从上至下，同一层结点(弧)从左至右规定了一个次序，则称T为有序树。 有序树的编号： v0 v1 v2 v3 v21 v22 v31 v211 v212 v213 * 离散数学 * m元(有序)树 定义14.3.4：设T是(有序)树，m ? 1。 ⑴若对T的每个结点v，均有d+(v) ? m，则称T为m元(有序)树 ; ⑵若对T的每个结点v，均有d+(v) = m或d+(v) = 0，则称T为完全m元(有序)树； ⑶若完全m元(有序)树的所有叶结点都在同一层，则称T为正则m元(有序)树 ; 当m=2时，分别称之为二叉树；完全二叉树； 正则二叉树。 * 离散数学 * 完全m元树上的数量关系 定理14.3.1 设T是一个完全m元树，其中有t个叶结点，i个分枝结点，于是 (m–1) ? i = t–1 证明：将m元树看成是每局有m位选手参加比赛的单淘汰赛计划表，树叶表示选手，分枝点i表示每局(分组赛)的冠军，根表示最后的冠军。 因为每局要淘汰(m–1)个人，因此，i局比赛共淘汰(m–1) ? i个人，最后剩下一位冠军。故有(m–1) ? i +1 = t ，整理得证. * 离散数学 * 应用举例 某机房有42台PC，公用一个电源插座，若每台PC只需一个插座，需要多少个4插座的接线板？ 解：一个有4插座的接线板可以连接4个接线板因此就构成了一个4元树。即接线板看成分枝结点， PC看成树叶。于是根据定理14.3.1有： i=(t – 1)/(m – 1)。 将t=42，m=4，代入上式可得 i=(42 – 1)/(4 – 1) = 13.66 ? 14 答：需要14个4插座的接线板。 * 离散数学 * 二叉树的应用 远程通讯中的编码问题：用0–1序列作为英文字母的传送信息。 (1)序列与字母如何对应？ (2)如何译码？ 编码应注意的事项： (1)使用频率越高的字母对应的码序列越短; (2)避免某一个字母对应的码是另一个字母所对应的码的前缀 . * 离散数学 * 前缀码 定义14.3.5：设?=b1b2…bn，bi∈{0, 1}是一个0-1序列(符号串)。序列?= b1b2…bi (1? i ? n)称为?的前缀。 例如,设?=010 , 则, 0 , 01 ,010都是?的前缀. 前缀码: 设Q ={?1, ?2, …, ?m}是一个0~1序列集合 . 如果Q中没有一个序列是另一个序列的前缀 , 则称Q为前缀码. * 离散数学 * 二叉树对应前缀码 定理14.3.2：任何一个二叉树的叶子可以对应一个前缀码 . 证明: 设T是一个二叉树，对T的每个分枝结点v，对以v为尾的弧(最多两条) ，将以左子结点为头的弧上标0，以右子结点为头的弧上标 1。于是从根结点出发到每个叶子结点的唯一通路中各弧上的标记依次连接而组成一个0 – 1序列。它们就是一组前缀码。 0 1 0 0 1 1 0 * 离散数学 * 前缀码对应二叉树 定理14.3.3：任