资源描述：
《9.1 无向树及生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、授课时间第十七周第2次课授课章节9.1无向树及生成树任课教师及职称唐新华讲师教学方法与手段板书和电子课件结合课时安排2课时使用教材和主要参考书1、教材：耿素云等，离散数学，清华大学出版社，20082.参考书左孝琳、李为槛、刘永才，离散数学（上海科技文献版）2006教学与目的要求：掌握树、生成树的概念以及图是树的几个等价命题教学重点、难点:重点：树及其性质、无向树的等价定义与性质、生成树、最小生成树难点：生成树存在条件、基本割集与基本割集系统教学内容:9.1无向树及生成树一、本节主要内容无向树、森林树枝、弦、余树生成树基本回路与基本回路系统基
2、本割集与基本割集系统最小生成树二、教学内容无向树无向树(树):连通而无回路的无向图，用T表示.平凡树:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点:树中度数³2的顶点右图为一棵12阶树.声明:本章中所讨论的回路均指简单回路或初级回路无向树的性质定理9.1设G=是n阶m条边的无向图，则下面各命题是等价的：（1）G是树(连通无回路);（2）G中任意两个顶点之间存在惟一的路径;（3）G中无回路且m=n-1;（4）G是连通的且m=n-1;（5）G是连通的且G中任何边均为桥;（6）G中没有回路,但在任何两个不
3、同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.无向树的性质(续)例题例1已知无向树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有2棵非同构的无向树,如图所示例题例2已知无向树T有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.求T的阶数n,并画出满足要求的所有非同构的无向树.解设T的
4、阶数为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棵非同构的无向树生成树生成树的存在性定理任何无向连通图都有生成树.证用破圈法.若图中无圈,则图本身就是自己的生成树.否则删去圈上的任一条边,这不破坏连通性,重复进行直到无圈为止,剩下的图是一棵生成树.推论1设n阶无向连通图有m条边,则m³n-1.推论2设n阶无向连通图有m条边,则它的生成树的余树有m-n+1条边.基本回路与基本回路系统定义设T是n阶m条
5、边的无向连通图G的一棵生成树，设e1¢,e2¢,…,e¢m-n+1为T的弦.设Cr为T添加弦er¢产生的G中惟一的圈(由er¢和树枝组成),称Cr为对应弦er¢的基本回路或基本圈,r=1,2,…,m-n+1.称{C1,C2,…,Cm-n+1}为对应T的基本回路系统.求基本回路的算法:设弦e=(u,v),先求T中u到v的路径Guv,再并上弦e,即得对应e的基本回路.基本割集与基本割集系统定义设T是n阶连通图G的一棵生成树,e1¢,e2¢,…,e¢n-1为T的树枝，Si是G的只含树枝ei¢,其他边都是弦的割集,称Si为对应生成树T由树枝ei¢生
6、成的基本割集,i=1,2,…,n-1.称{S1,S2,…,Sn-1}为对应T的基本割集系统.求基本割集的算法:设e¢为生成树T的树枝,T-e¢由两棵子树T1与T2组成,令Se¢={e
7、eÎE(G)且e的两个端点分别属于T1与T2}则Se¢为e¢对应的基本割集.实例例图中红边为一棵生成树,求对应它的基本回路系统与基本割集系统解弦e,f,g对应的基本回路分别为Ce=ebc,Cf=fabc,Cg=gabcd,C基={Ce,Cf,Cg}.树枝a,b,c,d对应的基本割集分别为Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,fg},S
8、d={d,g},S基={Sa,Sb,Sc,Sd}.无向图与最小生成树对无向图或有向图的每一条边e附加一个实数w(e),称作边e的权.图连同附加在边上的权称作带权图,记作G=.设G¢是G的子图,G¢所有边的权的和称作G¢的权,记作W(G¢).最小生成树:带权图权最小的生成树求最小生成树的算法——避圈法(Kruskal)设G=,将非环边按权从小到大排序：e1,e2,…,em.(1)取e1在T中(2)检查e2,若e2与e1不构成回路,则将e2加入T中,否则弃去e2.(3)检查e3,…,重复进行直至得到生成树为止.实例例
9、求图的一棵最小生成树复习思考题、作业题：设G=是n阶m条边的无向图，则下面各命题是等价的：（1）G是树(连通无回路);（2）G中任意两个顶点之间存在惟一的路径;（3）G
