非连通图的结点和弧经适当排列可得到为对角分块阵的关联矩阵.pptVIP

1 割边 图 G=(V,E) 中，eE。设 G=(V,Ee)，若G 的连通分支数目比G多1，则称e为G的一条割边。 定理3-1-1 上述e、G中，e是G的一条割边当且仅当 e不属于G中任何回路。 树 连通图G=(V,E)，若G中不含任何回路，则称G 为树。|V|=1时称之为平凡树。 3.1 树的基本概念 2 定理3-1-2 T=(V, E) 是结点数 n=|V| 1 的树，则下 述命题等价： T是无回路的连通图； T是连通的，且有n1条边； T有n1条边，且T中无回路； T是连通的，且T中的每一条边都是割边； T的任意两点间有且只有唯一的通路； T中无回路，但若在T的任一对不相邻的顶点之 间增加一条边，则构成T中的唯一回路。 3.1 树的基本概念 3 证明 上述定理内容也可作为树的等价定义。 推论1 任一非平凡树至少有两个结点的度为1。 推论2 G是一棵树当且仅当G是最小连通的（从G中去 除任意一边即破坏了G的连通性）。 3.1 树的基本概念 4 生成树 G=（V，E），若G的一个生成子图是一棵 树，则称之为G的一棵生成树（记为T）。G中在 T中的边称为（关于T的）树枝，G中不在T中的边 称为（关于T的）弦。G中的所有结点和弦构成的 子图称为（关于T的）余树。 余树不一定是树。 3.1 树的基本概念 5 定理3-1-3 任何连通图至少有一棵生成树。 证明 破圈法构造 推论1 设G=（V，E）连通，则|E|V|1 。 3.1 树的基本概念 6 关联矩阵 G=（V，A）中，设V=v1,v2,vn， A=a1, a2, am，令 B=(bij)nm，其中 1 aj=A bij= 1 aj=A 0 其它 称B为G的关联矩阵。 3.2 关联矩阵 7 例 a2a3 a4 a5 a6 a7a1 v1 v2 v3 v4 v5 v6 v7 3.2 关联矩阵 8 关联矩阵的特征： 每列有两个非零元+1、1； 孤立点对应的行为0向量； 非连通图的结点和弧经适当排列，可得到为对 角分块阵的关联矩阵。 3.2 关联矩阵 9 定理3-2-1 连通图 G=(V,A)的关联矩阵B的秩 r(B)2 转 ；否则计算结束，此时 det(Bk) = det(B2) 或 det(Bk) = -det(B2) ，易知 B2 的值只能为0、+1或-1。 3.2 关联矩阵 12 定理3-2-3 连通图 G=(V,A)的关联矩阵B的秩 r(B)=n-1，n=|V|。 证明 先证明 r(B) n-1。反证：若 r(B) A ，则称 u为v的父亲，v为u的儿子。若从u到v存在 有向道路，则称u是v的祖先，v是u的后代（子孙 ）。 3.4 有向树 28 树的高度 设有根树 T=(V, A)，v0为树根。u V的 深度是从v0 开始到达u的有向路的长度，T的高度 是从v到T的叶子的最长路的长度。 根结点深度为0，称为第0层； 深度同为i 的结点构成树的第i 层； 具有最大深度的结点的深度称为树的深度（高度 ）。 3.4 有向树 29 有序树 将各树的每个结点的所有儿子按次序排列 ，称这样的根树为有根有序树。 有序树的每个结点的出度小于或等于m时，称为m 元有序树。 有序树的每个结点的出度只为 0或 m 时，称为m 元正则有序树。 3.4 有向树 30 例 语法树 The big elephant ate the peanut Thebigelephantate the peanut 3.4 有向树 31 例 判定树：有8个硬币，已知其中有7个真币，一 个假币。假币的重量与真币不同。请使用一个天 平判定哪个是假币。 3.4 有向树 32 a+b+c d+e+f A+d b+e a bc aa dg ag a acdg g h ef bh g h = 3.4 有向树 33 二元树 二元树是2元有序树（各结点的出度不大于 2） 二元树的任一结点只可能具备四种形态之一： LRRL （） （） （） （ ） 3.5 二元树 34 满二元树 高度为k的二元树，除k层外其他各层结 点均有形态（）。 编号二元树 高度为k的满二元树，对其结点按从上 到下，同层结点从左到右的原则编号，得到结点 从12k+1-1 的编号序列。得到上述结点编号的二元 树称为编号二元树。 完全二元树 具有n个结点的二元树，若其构造与具 有不少于n个结点的编号二元树的前n个结点的构 造相同，则称之为一棵完全二元树。 3.5 二元树 35 高度为k的完全二元树，其k-1层以上结点构成一 棵高度为k-1 的满二元树。 理想二元树 高度为k的理想二元树，其k-1层以上 结点构成一棵高度为k-1 的满二元树。 正则二元树 每个结点的出度为 0或者2的二元树称 为一棵正则二元树（二元正则有序树）。 3.5 二元树 36 二元树的性质 第i 层的结点数最多为2i； 深度为k的二元树最多有2k+1-1个结点； 记二元树出度为2的结点数目为n2，叶子数目为 n0，则有： n0=n2+1 多元树与二元树的对应关系：以结点的最左儿 子为对应二元树中该结点的左儿子；以结点的 右兄弟为对应二元树中该结点的右儿子。 3.5 二元树 37 定义 给具有k个叶子结点的二元树的各个叶子分别 赋以非负实数权 pi (i=1,2,k)，并设对应的各个 叶子的深度分别为 li (i=1,2,k)，则称 为该树的带权外部通路总长。 最优二元树 具有k 个叶子结点且各个叶子分别被赋 以非负实数权 pi (i=1,2, k ) 的二元树中，具有最 小带权外部通路总长者称为相对于pi (i=1,2, k ) 的最优二元树。 3.6 Huffman树 38 Huffman 算法 给定k个非负实数，构造以它们为叶子带权且具有最小 M(T) 的最优二元树。 i k； 若 i =1 结束； 将 i 个非负实数权由小到大排列成序，以最小的两个数 作为左右儿子，构造其父亲结点，并以此左右儿子的 权值之和作为新构造的父亲结点的权值。在权序列中 删去此左右儿子对应的权值，增加新构造的父亲结点 的权值。 i i-1 ，转 (2)。 3.6 Huffman树 39 Huffman树 由Huffman算法构造的二元树称 为相对于非负实数权 pi (i=1,2, k) 的 Huffman树。 定理3-6-1 Huffman树是一棵相对于非负实 数权 pi (i=1,2, k) 的最优二元树。 3.6 Huffman树 40 p1 + p2 p1p2 3.6 Huffman树 证明 设非负实数权 p1 , p2 , p3 , , pk 且 p1 p2 p3 pk 。只须证明带权 p1 + p2 , p3 , , pk 的一 棵最优二元树，经过下列转换后可得一棵带权 p1 , p2 , p3 , , pk 的最优二元树。 41 3.6 Huffman树 非递减非负实数权序列 p1 , p2 , p3 , , pk 构成的一 棵最优二元树中， p1 , p2 必是一对兄弟。 证明：若p1没有兄弟，将其与其父亲结点重叠， 可得到一棵符合条件的M(T)更小的二元树，矛盾 。在具有最小M(T)的二元树中，权值最小的结点 必在最底层，故p1的兄弟只能是p2 （或与p2相等者 ） 42 (2)设上述 p1 , p2 , , pk 的一棵最优二元树 T 如下： p1p2 T TA 3.6 Huffman树 设T中 p1 , p2 路径长度均为d，则 M(T) =M(TA) + p1d + p2d TA p1 + p2 T1 构造T1 如图（此时 还不能肯定T1是一棵最优二元树） 则 M(T1) =M(TA) +( p1 + p2 )(d-1) 故 M(T1) = M(T) p1 p2 43 设带权 p1 + p2 , p3 , , pk （不一定非递减）的一棵最优二 元树为T1 如图，并构造带权 p1 , p2 , p3 , , pk 的二元树T （同样此时不能肯定T 是一棵最优二元树）。 p1 + p2 T1 TB 3.6 Huffman树 TB p1p2 T 44 显然有 M(T1) = M(T) p1 p2 注意到T1 为带权p1 + p2 , p3 , , pk 的一棵最优二元树， 即： M(T1 ) M(T1) 所以：M(T) p1 p2 M(T) p1 p2 或： M(T) M(T) 注意到T为带权 p1 , p2 , p3 , , pk 的一棵最优二元树，故 T也是一棵带权 p1 , p2 , p3 , , pk 的最优二元树。 至此，问题归结为求带权 p1 + p2 , p3 , , pk 的最优二元树 。 3.6 Huffman树 45 Huffman树是一棵正则二元树。 前缀码设 a1 a2 an-1 an 为长为n的符号串，称其子 串a1 , a1 a2 , , a1 a2 an-1分别为该符号串的长度 为1, 2, , n-1的前缀。设有符号串集合 A=1, 2, , m ，若其中对任意的 I , j A，ij，有i j 且互不为前缀，则称A是一个前缀码。 二元前缀码前缀码A=1, 2, , m 中的i 只由两 种符号（如0、1）组成时，称A为一个二元前缀码 。 3.6 Huffman树 46 定理3-6-2 对任意一棵正则二元树的叶子，都存在 唯一的一个二元前缀码。 例 P.314 图16-10 3.6 Huffman树 47 Huffman编码 以各个源码符号在源码电文中出现 的频率为权值，构造以源码符号为叶子的 Huffman树，得到关于源码符号集的一个二元前 缀码，称为其Huffman编码。 定理3-6-3 Huffman编码是关于该源码符号集的最 短二元前缀码。 证明 一段长度为N的源码电文，经过上述Huffman 编码译码后的译文长度为 M(T)*N，而Huffman树 是一棵最优二元树，具有最小的M(T)值。 3.6 Huffman树 48 实现译文长度最短的二元前缀码设计过程： q字频统计 q等概率假设 qHuffman树构造 qHuffman编码方案确定 例 设一段电文含