《9-1-树-离散数学-教学课件.ppt》由会员分享，可在线阅读，更多相关《9-1-树-离散数学-教学课件.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、作业讲评4P173:1 下列哪些能构成无向图度数列？这个不是简单图这个不是简单图（因含平行边）（因含平行边）P173:5 下列各无向图中有几个顶点？(2)21条边，3个4度顶点，其余均为3度顶点。解：设其余还有 n 个顶点，由握手定理得，所以，n=10。图中其有13个顶点。P173:5 下列各无向图中有几个顶点？(3)24条边，各顶点的度数是相同的。解：设共有 n 个顶点，度数均为k，由握手定理得，所以即要寻找方程的非负整数解：n、k均不可能同时为奇数，1 12 23 34 46 68 812124 48 82 24 41616n12346812 16 24 48k48 24 16 12864
2、321第9章 树 9.1 无向树及生成树9.2 根树及其应用最大支撑树问题n树是一类既简单而又非常重要的图，它是计算机中一种基本的数据结构和表示方法。n在输电网络分析、有机化学、最短连接及渠道设计等领域也都有广泛的应用，如：n某一地区有若干个主要城市，拟修建高速公路某一地区有若干个主要城市，拟修建高速公路把这些城市连接起来，使得其中任何一个城市把这些城市连接起来，使得其中任何一个城市都可以经高速公路直接或间接到达另一个城市，都可以经高速公路直接或间接到达另一个城市，设已知任意两个城市之间修建高速的成本，设已知任意两个城市之间修建高速的成本，那那么应如何决定在哪些城市间修建高速公路，使么应如何决
3、定在哪些城市间修建高速公路，使得总成本最小？得总成本最小？9.1 无向树及生成树n无向树无向树:连通无回路的无向图。连通无回路的无向图。n树叶树叶:树中度数为树中度数为1 1的顶点。的顶点。n分支点分支点:树中度数树中度数 2 2的顶点。的顶点。n规定：规定：平凡图也是树，叫平凡图也是树，叫平凡树。平凡树。n森林森林:每个连通分支都是树的非连通的无向图。每个连通分支都是树的非连通的无向图。n声明声明:本章中所讨论的回路均指简单回路或初级回路。本章中所讨论的回路均指简单回路或初级回路。(a)树(b)森林求出6个顶点的非同构无向树n顶点数n=6，树的边数m=n-1=5n树的总度数为n树中各顶点度数
4、分配情况可为(1)1,1,1,1,1,5 (2)1,1,1,1,2,4(3)1,1,1,1,3,3 (4)1,1,1,2,2,3(5)1,1,2,2,2,2无向树的性质 定理定理9.2 设设T 是是 n 阶非平凡的无向树，则阶非平凡的无向树，则T 中至少中至少有两片树叶有两片树叶.证证：由定理由定理9.1(树的定义树的定义)可知树可知树 T 共有共有n-1条边，条边，由握手定理得由握手定理得：设设 T 有有 k 片树叶，则片树叶，则 T 中的分支点为中的分支点为 n-k 个，每个，每个分支点的度数个分支点的度数 2，所有分支点度数之和，所有分支点度数之和 2(nk)，从，从而下式成立：而下式成
5、立：由上式解出由上式解出 k 2.例题2已知无向树T 有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.求T 的阶数n,并画出满足要求的所有非同构的无向树.解解 由树的性质得由树的性质得T的边数为的边数为 n 1,4度顶点的个数为度顶点的个数为 n(5+1+1)=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棵非同构的无向树棵非同构的无向树 生成树的存在性 n定理定理 任何无向连通图都有生成树任何无向连通图都有生成树.n证证：用破圈法用破圈法.
6、若图中无圈若图中无圈,则图本身就是自己的生成树则图本身就是自己的生成树.否则删去圈上的任一条边否则删去圈上的任一条边,这不破坏连通性这不破坏连通性,重复进行直到无圈为止重复进行直到无圈为止,剩下的图是一棵生成树剩下的图是一棵生成树.n推论推论1 1 设设n阶无向连通图有阶无向连通图有m条边条边,则则m n 1.n推推论2 设设n阶阶无无向向连连通通图图有有m条条边边,则则它它的的生生成成树树的的余树有余树有 m n+1条边条边.n推推论3 设设 为为G的的生生成成树树 T 的的余余树树，C 为为G 中中任任意一个圈，则意一个圈，则C与与 一定有公共边一定有公共边.基本回路与基本回路系统 n设设
7、T是是n阶阶m条条边边的的无无向向连连通通图图G的的一一棵棵生生成成树树，e1,e2,e m n+1为为T的弦的弦.n定义定义设Cr为T 添加弦添加弦er 产生的生的G中惟一的圈中惟一的圈(由由er 和和树枝枝组成成),n称称Cr为对应弦为对应弦er 的的基本回路基本回路或或基本圈基本圈。(r=1,2,m n+1)n 称称C1,C2,Cm n+1为对应为对应T的的基本回路系统基本回路系统.n求基本回路的算法:n设弦弦e=(u,v),n先求先求T中中u到到v的路径的路径 uv,再并上弦再并上弦e,n即得即得对应e的基本回路的基本回路.基本割集与基本割集系统 n设设T是是n阶连通图阶连通图G的一棵
8、的一棵生成树生成树,e1,e2,e n 1为为T的树枝，的树枝，n定义定义nSi是是G的的只只含含树枝枝ei,其其他他边都都是是弦弦的的割割集集,称称Si为对应生成生成树T由由树枝枝ei 生成的生成的基本割集基本割集,i=1,2,n 1.n称称S1,S2,Sn 1为对应T 的的基本割集系统基本割集系统.n求基本割集的算法:n设e 为生成生成树T的的树枝枝,T e 由两棵子由两棵子树T1与与T2组成成,n令令 Se=e|e E(G)且且e的两个端点分的两个端点分别属于属于T1与与T2 n则Se 为e 对应的基本割集的基本割集.基本割集与基本割集系统实例例 图中红边为一棵生成树,求对应它的基本割集
9、系统解：解：树枝树枝a,b,c,d对应的基本割集为对应的基本割集为 Sa=a,f,g,Sb=b,e,f,g,Sc=c,e,f g,Sd=d,g,S基基=Sa,Sb,Sc,Sd.无向图与最小生成树 n定义 n对对无无向向图图或或有有向向图图的的每每一一条条边边e附附加加一一个个实实数数w(e),称称作作边边e e的权的权.n图连同附加在边上的权称作图连同附加在边上的权称作带权图带权图,记作记作G=.n设设G 是是G的的子子图图,G 所所有有边边的的权权的的和和称称作作G 的的权权,记记作作W(G).n最小生成树:带权图中权最小的生成树。带权图中权最小的生成树。求最小生成树的算法避圈法(Krusk
10、al)设设G=,将非环边按权将非环边按权从小到大排序从小到大排序：e1,e2,em.(1)取取e1在在T中中(2)检查检查e2,若若e2与与e1不构成回路不构成回路,则将则将e2加入加入T中中,否则弃去否则弃去e2.(3)检查检查e3,重复进行直至得到生成树为止重复进行直至得到生成树为止.实例例例 求图的一棵最小生成树求图的一棵最小生成树 W(T)=38根树n根树的画法:n树根放上方树根放上方,省去所有有向边上的箭头省去所有有向边上的箭头n如右图所示n a 是是树根根n b,e,f,h,i 是是树叶叶n c,d,g是内点是内点n a,c,d,g 是分支点是分支点 第第0层：层：a 第第1层：层
11、：b，c 第第2层：层：d，e,f 第第3层：层：g，h 第第4层：层：i 树高：树高：4根树n顶点顶点v的层数的层数n在根树中，从树根到任意顶点在根树中，从树根到任意顶点v只能有唯一的一条路，只能有唯一的一条路，这条路的长度称为这条路的长度称为v的的级级(层层)数数。n树高:有向树中顶点的最大层数。有向树中顶点的最大层数。家族树n把根树看作一棵家族树:(1)若若顶点点 a 邻接接到到顶点点 b,则称称 b 是是 a 的的儿子儿子,a 是是 b 的的父父亲;(2)若若b和和c为同同一一个个顶点点的的儿儿子子,则称称b和和c是是兄弟兄弟;(3)若若a d且且a可可达达d,则称称a是是d的的祖祖先
12、先,d是是a的的后代后代.n根子树n设v为根根树的的一一个个顶点点且且不不是是树根根,称称v及及其其所所有有后后代代的的导出出子子图为以以v为根的根的.根树的分类n有序树有序树:将根树同层上的顶点规定次序将根树同层上的顶点规定次序.nr元有序树元有序树:有序的有序的r元树元树.nr元正则有序树元正则有序树:有序的有序的r元正则树元正则树.nr元完全正则有序树元完全正则有序树:有序的有序的r元完全正则树元完全正则树.二元有序树二元有序树二元正则有序树二元正则有序树二元完全正则有序树二元完全正则有序树1 21 2 3 41 21 21 2 3 41 2 3 4 5 6 7 81 21 2 31 2
13、最优2元树 n定义定义 n设设2元树元树T有有t片树叶片树叶v1,v2,vt,树叶的权分别为树叶的权分别为w1,w2,wt,n称称 为为T 的权的权,其中其中l(vi)是是vi的层数的层数.n在所有有t片树叶,带权w1,w2,wt 的 2元树中,权最小的2元树称为最优 2元树.求最优树的算法-Huffman算法n给定t片树叶的权为w1,w2,wt且w1 w2 wt。n连接权为w1，w2的两片树叶，得一分枝点，其权为w1w2 n在w1w2，w3，wt中选出两个最小的权，连接它们对应的结点(不一定是树叶)，得新分枝点及所带的权。n重复，直到形成t1个分枝点，t片树叶为止。W(T)等于所有分支点的权
14、之和等于所有分支点的权之和求带权为求带权为1,1,2,3,4,5的最优树的最优树.W(T)=38完全树中树叶数、分支节点数和m元完全正则树的关系 n在完全在完全m元完全正则树中，其树叶数为元完全正则树中，其树叶数为t，分支点数为分支点数为s，则，则(m-1)s=t-1。n证明：由所给条件知，该树有由所给条件知，该树有st个结点，个结点，由树的性质知，该树边数为由树的性质知，该树边数为st-1。另一方面，由完全另一方面，由完全m元树定义知：元树定义知：该树出度的和为该树出度的和为=ms =该树的边数该树的边数于是有于是有ms=st-1。整理后有整理后有(m-1)s=t-1。二元完全正则树二元完全正则树完全树中树叶数、分支节点数和m元完全正则树的关系举例n设有一台计算机，它有一条加法指令，可对3个数求和。如果要计算9个数的和，问至少要执行几次加法指令？n 解：用用3个结点表示三个数，用它们的父结点表示它们的和。个结点表示三个数，用它们的父结点表示它们的和。则问题就抽象为求一个完全则问题就抽象为求一个完全3元树的分支点有多少个。元树的分支点有多少个。把把9看成树叶的个数，则依据前面结论得看成树叶的个数，则依据前面结论得 (m-1)s=t-1 (3-1)s=9-1，s=4。所以要执行所以要执行4次加法指令。次加法指令。作业 20P203：1，2，5，7，8