离散数学-第16章-树

本章的主要内容无向树及其性质生成树根树及其应用本章的先行知识是第十四章第十六章树一、无向树的定义及主要定理1．无向树的定义定义16.1（1）无向树——连通无回路的无向图（2）平凡树——平凡图（3）森林——至少由两个连通分支（每个都是树）组成（4）树叶——1度顶点（5）分支点——度数2的顶点图1为9阶树.第一节无向树及其性质2．无向树的等价定义与性质定理16.1设G=V,E是n阶m条边的无向图，则下面各命题是等价的：（1）G是树（2）G中任意两个顶点之间存在惟一的路径.（3）G中无回路且m=n1.（4）G是连通的且m=n1.（5）G是连通的且G中任何边均为桥.（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈.(1)(2)如果G是树，则G中任意两个顶点之间存在唯一的路径。存在性。由G的连通性及定理14.5的推论（在n阶图G中，若从顶点vi到vj(vivj)存在通路，则vi到vj一定存在长度小于等于n-1的初级通路(路径)）可知，u,v∈V，u与v之间存在路径。唯一性（反证法）。若路径不是唯一的，设Г1与Г2都是u到v的路径，易知必存在由Г1和Г2上的边构成的回路，这与G中无回路矛盾。(2)(3)如果G中任意两个顶点之间存在唯一的路径，则G中无回路且m＝n-1。首先证明G中无回路。若G中存在关联某顶点v的环，则v到v存在长为0和1的两条路经(注意初级回路是路径的特殊情况)，这与已知矛盾。若G中存在长度大于或等于2的圈，则圈上任何两个顶点之间都存在两条不同的路径，这也与已知矛盾。(2)(3)如果G中任意两个顶点之间存在唯一的路径，则G中无回路且m＝n-1。其次证明m＝n-1。（归纳法）n＝1时，G为平凡图，结论显然成立。设n≤k(k≥1)时结论成立，当n=k+1时，设e＝(u,v)为G中的一条边，由于G中无回路，所以G-e为两个连通分支G1、G2。设ni、mi分别为Gi中的顶点数和边数，则ni≤k，i＝1,2，由归纳假设可知mi＝ni-1，于是m＝m1+m2+1＝n1-1+n2-1+1＝n1+n2-1＝n-1。只需证明G是连通的。（采用反证法）假设G是不连通的，由s(s≥2)个连通分支G1,G2,…,Gs组成，并且Gi中均无回路，因而Gi全为树。由(1)(2)(3)可知，mi＝ni-1。于是，由于s≥2，与m＝n-1矛盾。111(1)sssiiiiiimmnnsns(3)(4)如果G中无回路且m＝n-1，则G是连通的且m＝n-1。如果G是连通的且m＝n1，则G是连通的且G中任何边均为桥。只需证明G中每条边均为桥。e∈E，均有|E(G-e)|＝n-1-1＝n-2，由习题十四题49（若G是n阶m条边的无向连通图，则m≥n-1）可知，G-e已不是连通图，所以，e为桥。(4)(5)如果G是连通的且G中任何边均为桥，则G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。因为G中每条边均为桥，删掉任何边，将使G变成不连通图，所以，G中没有回路，也即G中无圈。又由于G连通，所以G为树，由(1)(2)可知，u,v∈V，且u≠v，则u与v之间存在唯一的路径Г，则Г∪(u,v)（(u,v)为加的新边）为G中的圈，显然圈是唯一的。(5)(6)如果G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈，则G是树。只需证明G是连通的。u,v∈V，且u≠v，则新边(u,v)∪G产生唯一的圈C，显然有C-(u,v)为G中u到v的通路，故u～v，由u,v的任意性可知，G是连通的。(6)(1)定理16.2设T是n阶非平凡的无向树，则T中至少有两片树叶.证设T有x片树叶，由握手定理及定理16.1可知，)(2)()1(2xnxvdni由上式解出x2.二、解无向树与画非同构的无向树例已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树.解解本题用树的性质m=n1，握手定理.设有x片树叶，于是n=1+2+x=3+x,2m=2(n1)=2(2+x)=13+22+x解出x=3，故T有3片树叶.T的度数列应为1,1,1,2,2,3易知3度顶点与1个2度顶点相邻与和2个2度顶点均相邻是非同构的，因而有2棵非同构的无向树T1,T2，见图2所示.图2例已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点的度数均为4，求T的阶数n，并画出满足要求的所有非同构的无向树.解设T的阶数为n,则边数为n1，4度顶点的个数为n7.由握手定理得2m=2(n1)=51+21+31+4(n7)解出n=8，4度顶点为1个.T的度数列为1,1,1,1,1,2,3,4，共有3棵非同构的无向树，见图3所示.图3一、生成树及其存在条件1．定义定义16.2设G为无向图（1）G的树——T是G的子图并且是树（2）G的生成树——T是G的生成子图并且是树（3）生成树T的树枝——T中的边（4）生成树T的弦——不在T中的边（5）生成树T的余树T——全体弦组成的集合的导出子图注意：T不一定连通，也不一定不含回路，见图4中所示图4第二节生成树2．生成树存在条件定理16.3无向图G具有生成树当且仅当G连通.证必要性显然.充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）推论1G为n阶m条边的无向连通图，则mn1.推论2T的边数为mn+1.推论3T为G的生成树T的余树，C为G中任意一个圈，则C与T一定有公共边.证否则，C中的边全在T中，这与T为树矛盾.二、基本回路系统与基本割集系统1．基本回路与基本回路系统（1）定义基本回路的基础定理16.4设T为G的生成树，e为T的任意一条弦，则Te中含一个只有一条弦其余边均为T的树枝的圈.不同的弦对应的圈也不同.证设e=(u,v)，在T中u到v有惟一的路径（定理16.1），则e为所要求的圈.（2）基本回路与基本回路系统的定义定义16.3设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,…,emn+1为T的弦.设Cr为T添加弦er产生的G中只含弦er，其余边均为树枝的圈.称Cr为G的对应树T的弦er的基本回路或基本圈，r=1,2,…,mn+1.并称{C1,C2,…,Cmn+1}为G对应T的基本回路系统，称mn+1为G的圈秩，记作(G).（3）求基本回路的算法：设弦e=(u,v)，先求T中u到v的路径uv，再并上弦e，即得对应e的基本回路.对应生成树的弦分别为e6,e7,e8,e10,e11。设它们对应的基本回路分别为C1,C2,C3,C4,C5，从对应的弦开始，按逆时针（也可都按顺时针）的顺序写出它们，分别为此图的圈秩为5，基本回路系统为{C1,C2,C3,C4,C5}。无向连通图G的圈秩与生成树的选取无关，但不同生成树对应的基本回路系统可能不同。说明求下图中的基本回路系统。举例C1＝e6e4e5C2＝e7e2e1C3＝e8e9e2e1C4＝e10e3e5e2C5＝e11e3e5e2e92．基本割集与基本割集系统（1）定义基本割集的基础定理16.5设T是连通图G的一棵生成树，e为T的树枝，则G中存在只含树枝e，其余边都是弦的割集，且不同的树枝对应的割集也不同.证由定理16.1可知，e是T的桥，因而Te有两个连通分支T1和T2，令Se={e|eE(G)且e的两个端点分别属于V(T1)和V(T2)}，由构造显然可知Se为G的割集，eSe且Se中除e外都是弦，所以Se为所求.显然不同的树枝对应的割集不同.（2）基本割集与基本割集系统的定义定义16.4设T是n阶连通图G的一棵生成树，e1,e2,…,en1为T的树枝，Si是G的只含树枝ei的割集，则称Si为G的对应于生成树T由树枝ei生成的基本割集，i=1,2,…,n1.并称{S1,S2,…,Sn1}为G对应T的基本割集系统，称n1为G的割集秩，记作(G).（3）求基本割集的算法设e为生成树T的树枝，Te为两棵小树T1与T2，令Se={e|eE(G)且e的两个端点分别属于T1与T2}则Se为e对应的基本割集.树枝为e1,e2,e3,e4,e5,e9。设它们对应的基本割集分别为S1,S2,S3,S4,S5,S6。此图的割集秩为6，基本割集系统为{S1,S2,S3,S4,S5,S6}。S1＝{e1,e7,e8}无向连通图G的割集秩与生成树的选取无关，但不同生成树对应的基本割集系统可能不同。说明求下图中的基本割集系统。举例S2＝{e2,e7,e8,e10,e11}S3＝{e3,e10,e11}S4＝{e4,e6}S5＝{e5,e6,e10,e11}S6＝{e9,e8,e11}三、最小生成树1．定义定义16.5T是G=V,E,W的生成树（1）W(T)——T各边权之和（2）最小生成树——G的所有生成树中权最小的2．求最小生成树的一个算法避圈法（Kruskal）设G=V,E,W，将G中非环边按权从小到大排序：e1,e2,…,em.（1）取e1在T中（2）查e2，若e2与e1不构成回路，取e2也在T中，否则弃e2.（3）再查e3,…,直到得到生成树为止.例16.3求下图所示两个图中的最小生成树。W(T1)＝6W(T2)＝12例求图6所示图的一棵最小生成树.图6所求最小生成树为图7所示，W(T)=38.图7一、根树及其分类1．根树的定义定义16.6T是有向树（基图为无向树）（1）T为根树——T中一个顶点入度为0，其余的入度均为1.（2）树根——入度为0的顶点（3）树叶——入度为1，出度为0的顶点（4）内点——入度为1，出度不为0的顶点（5）分支点——树根与内点的总称（6）顶点v的层数——从树根到v的通路长度（7）树高——T中层数最大顶点的层数（8）平凡根树——平凡图第三节根树及其应用2.根树的画法——树根放上方，省去所有有向边上的箭头图8中给出3棵根树（1）（2）（3）图83.家族树定义16.7T为非平凡根树（1）祖先与后代（2）父亲与儿子（3）兄弟4．根子树定义16.8设v为根树T中任意一顶点，称v及其后代的导出子图为以v为根的根子树.5．根树的分类（1）T为有序树——同层上顶点标定次序（2）分类①r叉树——每个分支点至多有r个儿子②r叉有序树——r叉树是有序的③r叉正则树——每个分支点恰有r个儿子④r叉正则有序树⑤r叉完全正则树——树叶层数相同的r叉正则树⑥r叉完全正则有序树二、根树的应用1．最优二叉树（简称最优树）（1）定义定义16.9设2叉树T有t片树叶v1,v2,…,vt，权分别为w1,w2,…,wt，称)()(1itiivlwtW为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中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权.③重复（2），直到形成t1个分支点，t片树叶为止.例求带权为1,1,2,3,4,5的最优树.解题过程由图9给出，W(T)=38图92.最佳前缀码（1）前缀码的定义定义16.10设1,2,…,n-1,n是长度为n的符号串①前缀——1,12,…,12…n1②前缀码——{1,2,…,m}中任何两个元素互不为前缀③二元前缀码——i(i=1,2,…,m)中只出现两个符号，如0与1.（2）如何产生二元前缀码？定理16.6一棵2叉树产生一个二元前缀码.推论一棵正则2叉树产生惟一的前缀码（按左子树标0，右子树标1）图10所示树产生的前缀码为{00,10,11,011,0100,0101}图10（3）用Huffman算法产生最佳前缀码例（书上例16.6