第七章 树 7.1树及其性质 定义 7.1：一个连通无回路的图称为树,记为T。树中度数为1的顶点称为树叶(或称悬挂点)。度数大于1的顶点称为分枝点或内点。不相交的树的全体称为森林。平凡图也可称为平凡树。(平凡图即只有一个点)

图 (a)是一棵树；(b)是森林,也就是无回路的图,它的每个分支是一棵树。

除了定义 7.1 给出树的定义外还有几个树的等价定义, 即下面的定理。 定理7.1：设图T有n个顶点,有下列6条T是树的等价定义: (1)T是无回路的连通图; (2)T是无回路图,且e=n-1,其中e是边数; (3)T是连通图,且e=n-1; (4)T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路(称T为最大无回路图); (5)T是连通图,但删去任一边后,便不连通(称T为最小连通图); (6)T的每一对不同的顶点之间有唯一的一条路。

证明：(1)→(2): T是无回路的连通图要证明T是无回路图,且e=n-1，即证明e=n-1 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图，显然只能是下图所示： 故结论成立。 假设n=k时结论成立,现考察n=k+1时,由于连通无回路以及定理 5.4 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为1的点u,它的关联边为 {u,v}。

(2)→(3): T是无回路图,且e=n-1,要证明T是连通图,且e=n-1。即证明T是连通图,用反证法,

(3)→(4):在T是连通图,且e=n-1的条件下,证明T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路。 n=2时e=1,且连通, 只能是下图 显然T是无回路的。

假设n=k-1时结论成立,考察n=k时,由于T是连通的,所以,每个顶点度数1(e=k-1)。可以证明,至少存在一个顶点u,使 d(u)=1。Why?

2)再证明如果在连通图T的任两个不相邻顶点之间添加一边,记为{vi,vj},则该边与T中从vi到vj的一条路 (vi,vi1,…, vis,vj) 构成一条回路(vi,vi1,…, vis,vj,vi)。 若这条回路不唯一，由于T无回路，而T∪{vi,vj}得到了回路，因此另一条回路C'也含有边{vi,vj}，

(4)→(5): 在T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路的条件下证明T是连通图,但删去任一边后,便不连通。 若T不连通, 则存在顶点vi和vj,在vi与vj之间没有路。显然,若加一边{vi,vj},不会产生回路,与假设矛盾。 又由于T无回路,则删去任一边,便不连通

(5)→(6): 在T是连通图,但删去任一边后,便不连通的条件下证明T的每一对不同的顶点之间有唯一的一条路。 由于T是连通的,任两点之间有一条路。如果某两个顶点之间多于一条路,则T中必含有回路,(Why?) 删去该回路上任一边,图仍连通,与假设矛盾。 (6)→(1): 在T的每一对不同的顶点之间有唯一的一条路的条件下，证明T是无回路的连通图。显然图是连通的。若有回路, 则回路上任两点之间有两条路, 从而导致矛盾。

推论：若G是n个顶点个分支的森林, 则G有n-条边。 定理7.2:在任一棵非平凡树T中, 至少有两片树叶。 证明:由于T是连通的,对T的任一顶点vi,d(vi)1,并且e=n-1,即所有顶点度数之和=2(n-1). 下面证明T中至少有两个顶点的度数为 1 。

7.2生成树与割集

例如下图中给定图G,粗线表示G的生成树T,它的边集是{e1,e4,e5,e6},的边集是{e2,e3,e7,e8}。

定理7.3：G是连通图当且仅当G有生成树。 证明：1) G有生成树证明G是连通图。因为生成树是连通图,生成子图连通，则原图一定连通。 2) G是连通图证明G有生成树 设G是连通图,若G没有回路,则G本身就是生成树； 若G只有一条回路,从这条回路中删去一条边, 仍保持连通, 得到一棵生成树； 若G中有多条回路, 则重复上述过程, 直到得到一棵生成树为止。

设连通图G有n个顶点, e条边, 那么G的任一棵生成树有n-1条枝, e-n+1条连枝。 设图G有n个顶点,e条边, 个分支, n,e,之间有两个简单的关系式: n-0; e-n+0。 定义 7.3:设图G有n个顶点, e条边, 个分支, 称n-为G的秩, 称e-n+为图G的零度。 显然G的秩是G的各分支中生成树的枝数之和, G的零度是G的各分支中生成树的连枝数之和。 对于连通图G来说, 它的秩为n-1, 零度为e-n+1。

定义7.4：设D是图G的一个边集, 若在G中删去D的全部边后所得图的秩减少 1 , 而删去D的任何真子集均无此性质, 称D为G的割集。 二、割集与断集 定义7.4：设D是图G的一个边集, 若在G中删去D的全部边后所得图的秩减少 1 , 而删去D的任何真子集均无此性质, 称D为G的割集。 图 (a) 中边集{e1, e3,e5,e6,e8}是割集，但删去任何真子集不具有此性质

图(b)中边集{e1, e2} 是割集 边集{ e1,e2,e3,e4} 不是割集,

定义7.5:设图G的顶点非空真子集为V1V, 在G中一个端点在V1中, 另一端点在V(G)-V1中的所有边组成的集合称为G的一个断集或称边割,记为 E(V1(V(G)-V1)), 简记为(V1, V(G)-V1)。 当|(V1, V(G)-V1)|=1时, (V1, V(G)-V1)中的那条边称为割边或 桥。 图 7.2(b) 中边集{e1,e2}和{e1,e2,e3,e4}都是断集(边割)。 割集是断集, 反之不一定。

定义7.5:设图G的顶点非空真子集为V1V, 在G中一个端点在V1中, 另一端点在V(G)-V1中的所有边组成的集合称为G的一个断集或称边割,记为 E(V1(V(G)-V1)), 简记为(V1, V(G)-V1)。 当|(V1, V(G)-V1)|=1时, (V1, V(G)-V1)中的那条边称为割边或 桥。 图 7.2(b) 中边集{e1,e2}和{e1,e2,e3,e4}都是断集(边割)。 割集是断集, 反之不一定。

对于连通图G(V,E), 删去一个割集D, 得到两个分支, 顶点集分别为V1和V(G)-V1, 割集D是G中一个端点在V1中, 另一端点在V(G)-V1中的边的全体。 如果在连通图G中, 删去一个断集而不是一个割集, 那么将得到多于两个分支。

三、割集与回路 定理7.4：任何一条回路和任何生成树的余树至少有一条公共边。 证明：如果一条回路和一棵生成树的余树没有公共边, 则这回路含在该生成树中, 这是不可能的。 定理7.5：任何一个割集和任何生成树至少有一条公共边。 证明：如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说, 删去一个割集后, 不能将图G分为两个分支, 这与割集的定义相矛盾。

定理7.6：任何一个回路和任何一个割集有偶数条公共边。 证明：从连通图G中删去一个割集D后, 得到两个顶点子集V1和V2, 考察G中任一条回路C : (1) 如果C中所有顶点在V1(或V2)中, 则C与D没有公共边。 (2)如果C中顶点既有一些在V1中, 又有一些在V2中, 先看D中任何一边, 它的一个端点在V1中, 另一个端点在V2中, 且G中除D中边以外, 不再有任何边连接V1与V2中的顶点。

定义7.6：设连通图G中给定生成树T, 对于只包含T中一条枝的割集,称此割集为关于T的基本割集。 因为从生成树T中删去一条枝, 将T分为两棵树, 它将G的顶点集V划分为V1和V-V1, 在G中这两个顶点集之间的连边, 便对应这一枝的唯一的基本割集。

设连通图G有e条边, n个顶点, 给定的生成树T应有n-1条枝, 所以恰有n-1个基本割集, 这些基本割集的全体称为生成树T基本割集组。 定义7.7:设连通图G中给定生成树T, 在T中加一条弦, 恰产生一条回路, 称此回路为关于T的基本回路。 由定理 7.1 的等价定义 (4) , 可知在T中加一弦, 产生唯一的回路。 设连通图G有e条边, n个顶点, 给定的生成树应有n-1条枝, e-n+1条弦, 所以恰有e-n+1条基本回路, 这些基本回路的全体称为生成树T的基本回路组。 例如图(a)中给定T={e1,e4,e5,e6}, 关于T的基本割集组: {e1,e2,e8},{e4,e3,e2,e8},{e5,e3, e2, e7}, {e6,e7} 基本回路组: {e2,e1,e4,e5},{e3, e4, e5},{e7,e5,e6},{e8,e1,e4,}

7.3最小生成树 定义7.10:设G(V,E,w)是带权连通简单图, w是从E到实数集的函数。又设T是G的一棵生成树,T中所有枝的权之和称为T的权,记为W(T)。具有权 minTW(T)的生成树称为最小生成树。 这个问题是具有实际意义的。例如G的顶点表示城市, G的边表示城市间的道路,边的权表示对应道路的长度, 现在沿着道路架设通讯线路, 将这些城市联系起来, 要求架设的线路最短, 这个问题就是求一棵最小生成树的问题

克鲁斯科尔算法的步骤, 通俗地说, 就是先将G中的边按权从小到大顺序排列, 再从小到大依次取出每一边作检查。 一开始取权最小的边{v1,v6}为e1,且w(e1)=l,由e1导出一个部分子图,然后依次每取一边加入已得部分子图。 若保持无回路, 将该边与原有部分子图中边导出一个新的部分子图;若得到回路, 将该边放弃。 上述过程继续进行, 直到所有边均检查完, 得到的部分子图就是所求的一棵最小生成树, 如图(b)所示, 这里e1={v1,v6}和e2={v7,v2}取出后,取e3为{v2,v3},;

若改取e3为{v3,v7},可得到另一棵最小生成树 求最小生成树的克鲁斯科尔(Kruskal)算法

克鲁斯科尔算法:设G(V,E,w)是有n个顶点的带权连通简单图。 (1)选取G的一边e1,使w(e1)最小,令E1={e1},1i。 (2)若已选Ei={e1,e2,,ei},那么从E-Ei中选取一边ei+1,满足: 1)Ei∪{ei+1}的导出子图中不含有回路; 同时 2)w(ei+1)为满足1)E-Ei中的最小; 3)若ei+1存在,则令Ei+1=Ei∪{ei+1},i+1i,转(2); 若ei+1不存在,则停,此时Ei导出的子图就是所求的最小生成树,记为T。

定理7.8:克鲁斯科尔算法所得到的图T是最小生成树。 证明:首先由定理7.1等价定义(4)(T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路)知T是G的一棵子树。 并由等价定义(2)可知边数为n-1(T是无回路图,且e=n-1)，所以为G的生成树。 下面证明T是最小生成树即可。

用反证法证明, 假设T不是G的最小生成树,而S是G的生成树, 并且 W(S)<W(T)。 在生成树T中有n-1条边。 按权从小到大的顺序排列为e1,e2,,ek,,en-1。 若ek是不在S中的第一条边, 也就是说e1,e2,,ek-1是S和T的公共边。 现在对S进行变换,在S上加边ek得到一条回路, 记为C ,在C中必有一边e‘S, 但e’T,否则T中有回路,导致矛盾。 但因为e1,e2,,ek-1是S和T的公共边, e‘S,所以e1,e2,,ek-1和e’不构成回路, 根据克鲁斯科尔算法知w(ek)≤w(e')(否则T应选e')。

现从S∪ek中删去e‘,得到生成树S’,由于w(ek)≤w(e‘),所以W(S’)≤W(S),并且S‘与T的公共边比S与T的公共边多一条 重复上述过程,每一步作一次树的变换, 使总权数减少, 最后生成树S变换到生成树T,W(T)≤W(S), 与假设 W(S)<W(T)相矛盾。

7.5有根树与二分树 定义7.11：有向图在不考虑弧的方向时是一棵树, 称该有向图为有向树。 显然有向树是弱连通的。现在将讨论一类重要的有向树, 即有根树, 定义如下: 定义7.12：若一棵有向树恰有一个顶点的入度为 0 ,其余所有顶点的入度均为1,则称该有向树为有根树。入度为 0 的顶点称为有根树的根。出度为0的顶点称为有根树的树叶。出度非零的顶点称为分枝点或内点。

在有根树中,从根v到其余每个顶点有唯一的一条有向路。这一性质由定义 7.12 即可得出。有根树中还有一些专门术语, 现在介绍如下: 定义7.13：设u是有根树的分枝点, 若从u到w有一条弧 (u,w),则称w为u的儿子,或u为w的父亲。若一个顶点有两个儿子, 则称它们为兄弟。若从u到z有一条有向路, 则称z是u的子孙,或称u是z的祖辈。从根到某一顶点v的路长度称为顶点v的层数。从根到树叶的最大层数, 称为有根树的高。

如图是有根树, 顶点标号写在圆圈中。顶点 1 是根, 顶点 6, 8, 9, 10, 11, 12 都是树叶, 顶点 1, 2, 3, 4, 5, 7 都是分枝点, 顶点 1 的层数为 0 , 顶点 2, 3的层数为 1 , 顶点 4, 5, 6, 7, 8 的层数为 2 , 顶点 9, 10, 11, 12 的层数为 3 。

有根树的概念非常重要, 原因在于它描述了一个离散结构的层次关系, 而层次结构是一种重要的数据结构, 所以有根树结构在相当广泛的领域中有它的应用。有时只要考虑某一层次上某分枝点为根的局部层次关系, 因此引入下面的概念: 定义7.14：设u是有根树T的任一顶点,以u为根,u及其所有子孙所组成的顶点集记为V',u到这些子孙的有向路上所有弧组成的弧集记为E',称T的子图T'(V',E')为以u为根的子树。

前面讨论有根树时, 没有考虑同一分枝点连出的弧的次序, 例如图 所示的有根树就是这样, 它们是相同的有根树。但是在计算机科学中的许多具体问题(如编码理论和程序语言等)一定要考虑这种弧的次序。为此,现在引进有序树的概念。

定义7.15：有根树的每个分枝点连出的弧(或者有根树的每一个顶点)从左到右用正整数1,2,,i,标上标号,称该有根树为有序树。 在确定树或画树的方式中,这些标号如果清楚的话, 那么标号可以省略。 如下面2个图中的有序树是不同构的, 对应的有根树却相同, 即如上图(a)、(b)所示。 (c)可表示一个人的长子有三个孩子, 次子没有孩子; (d)可表示一个人的长子没有孩子,而次子有三个孩子 。

定义7.16:在有序树中,每个分枝点v至多有m个儿子,称该有序树为m分树。如果每个分枝点恰有m个儿子,称该有序树为正则m分树。 在画有序树时,如果规定将一个分枝点的儿子放在它下面, 那么弧的箭头就可以省略, 因为箭头总是朝下的。如前面例子中的图。

例:算术表达式a-(b+(c/d)+(e/f))可以用图中的二分树来表示。所有运算对象都处于树叶的位置, 所有运算符处于分枝点的位置。如果将分枝点连出的弧的次序改变一下, 那么所得到的二分树对应的算术表达式也就改变了。

定理7.10:在正则二分树中,它的分枝点数i和树叶数t满足:i=t-1。 因此有2i=i+t-1, 所以i=t-1。 类似可证在正则m分树中有(m-1)i=t-1。

定理7.11：设T是正则二分树,I表示所有分枝点的路长度之总和,E表示所有树叶的路长度之总和, 则E=I+2i,其中i是分枝点数。 证明：对分枝点数i进行归纳证明,当i=1时E=2,I=0,所以E=I+2i。

假设i=k-1时结论成立。 现考察分枝点数i=k的情况,设分枝点v的两个儿子是树叶,删去v连出的边及其儿子,v的路长度为l, 由归纳假设知, 在T'中,E'=I'+2(k-1)。 类似可证在正则m分树中有E=(m-1)I+mi, 具体证明作为习题。

7.6最优树 考虑远距离通讯中的一个问题,一篇英文字母组成的短文如何从发送端发出信息, 通过远距离传输送到接收端。 通常的电报是用长度为5的0和1序列来表示英文字母和标点符号的, 这种长度为5的0和1序列组成的集合称为5单位编码。 为了传输一篇短文,将对应的0和1序列组成的信息串发送出去以后, 在接收端就将此信息串划分成长度为 5 的序列, 这样就得到对应的短文。

但在一篇短文中每个字母出现的频率是不同的, 如表所示。 例如e,t的频率要比j,z的频率大很多。为了使短文对应的信息串的总长度缩短, 首先要求出现次数多的字母用较短的 0 和 1 序列表示, 出现次数少的字母用较长的 0 和 1 序列表示;

其次要求在接收端能从一个信息串中明确地分辨出字母所对应的序列。例如字母 a,b,c,d,e分别用下列 0 和 1 序列表示, 对应关系如下: 00 110 010 10 01 把集合{00,110,010,10,01}叫做码。 如果接收端收到信息串是010010, 这时分辨不清发送来的是ead还是cc,这是因为e对应的序列是c对应序列的前缀。 为了避免此情况的发生, 只要将c对应的序列改为111,那么才能确定送来的是ead。 集合{00,110,111,10,01}就叫前缀码。

定义7.17：二进制有限序列组成的集合称为码。其中每个元素称为一个码字。在一个码中,任一码字都不是其它码字的前缀, 称该码为二元前缀码,简称前缀码。 为了设计 26 个英文字母所对应的前缀码, 先来看前缀码与二分树的关系。 定理7.12：给定一棵二分树, 则可确定一个前缀码。反之, 对应于一个前缀码, 存在一棵二分树。 证明

对于图 7.12 中的前缀码来说, 若我们接收到信息串序列为 000011001, 那么可以从图的二分树树根出发, 依序列的次序, 当遇到 0 时, 就沿着标记为 0 的边走;当遇到 1 时, 就沿着标记为 1 的边走, 一直走至树叶, 这样前缀码中的一个序列就被找到。 然后再回到根, 用同样方法可以找出下一个序列。这样的过程保证使信息串序列总可分割成前缀码中的序列。于是从信息串序列 000011001 可以得到对应的英文字母aabe。

霍夫曼算法:设n个权w1,w2,,wn,w1w2wn

于是得到n-1棵树, 它们的根分别带权w1+w2,wn, (此时w1+w2w3不一定成立)。再在n-1棵树中找出两棵根带权最小的树, 合并为一棵新的二分树, 使得这两棵树分别是它的左、右子树, 新的二分树的根带的权为原两棵树根带的权之和, 每一步选择两棵根带权最小的树合并为一棵二分树, 重复这一过程直到只有一棵二分树为止。可以证明这棵树是带权w1,w2,,wn的最优树。 例:构造带权 2,4,7,8,10,12 的最优树。构造过程如图所示。

这棵最优树的权为:2*4+4*4+7*3+12*2+8*2+10*2=105 一般来说, 带权w1,w2,,wn的最优树不一定是唯一的。

作业: P154 9,12,14,15, 17,18,19,20,21,22