代数结构与图论16章.ppt

《代数结构与图论16章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十六章树主要内容无向树及其性质生成树根树及其应用116.1无向树及其性质定义16.1(1)无向树——连通无回路的无向图(2)平凡树——平凡图(3)森林——至少由两个连通分支（每个都是树）组成(4)树叶——1度顶点(5)分支点——度数2的顶点2无向树的等价定义定理16.1设G=是n阶m条边的无向图，则下面各命题是等价的：(1)G是树(2)G中任意两个顶点之间存在惟一的路径.(3)G中无回路且m=n1.(4)G是连通的且m=n1.(5)G是连通的且G中任何边均为桥.(6)G中没有回路，但在任何两个不同的顶点之间加一条新边，

2、在所得图中得到惟一的一个含新边的圈.3(3)(4).只需证明G连通.用反证法.否则G有s（s2）个连通分支都是小树.于是有mi=ni1,，这与m=n1矛盾.证明思路(2)(3).若G中有回路，则回路上任意两点之间的路径不惟一.对n用归纳法证明m=n1.n=1正确.设nk时对，证n=k+1时也对：取G中边e，Ge有且仅有两个连通分支G1,G2(为什么?).nik，由归纳假设得mi=ni1,i=1,2.于是，m=m1+m2+1=n1+n22+1=n1.(1)(2).关键一步是,若路径不惟一必有回路.4(4)(5)

3、.只需证明G中每条边都是桥.为此只需证明命题“G是n阶m条边的无向连通图，则mn1”.命题的证明:对n归纳.eE,Ge只有n2条边，由命题可知Ge不连通，故e为桥.证明思路(5)(6).由(5)易知G为树，由(1)(2)知，u,vV（uv）,u到v有惟一路径，加新边(u,v)得惟一的一个圈.(6)(1).只需证明G连通，这是显然的.5由上式解出x2.定理16.2设T是n阶非平凡的无向树，则T中至少有两片树叶.无向树的性质证设T有x片树叶，由握手定理及定理16.1可知，6例题例1已知无向树T中有1个3度顶点，2

4、个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，如图所示.7例2已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点的度数均为4，求T的阶数n，并画出满足要求的所有非同构的无向树.例题解设T的阶数为n,则边数为n

5、1，4度顶点的个数为n7.由握手定理得2m=2(n1)=51+21+31+4(n7)解出n=8，4度顶点为1个.8T的度数列为1,1,1,1,1,2,3,4，共有3棵非同构的无向树，如图所示.例题9不一定连通，也不一定不含回路，如图所示定义16.2设G为无向图(1)G的树——T是G的子图并且是树(2)G的生成树——T是G的生成子图并且是树(3)生成树T的树枝——T中的边(4)生成树T的弦——不在T中的边(5)生成树T的余树——全体弦组成的集合的导出子图16.2生成树10推论2的边数为mn+1.推论3为G的生成树T的余树，

6、C为G中任意一个圈，则C与一定有公共边.证否则，C中的边全在T中，这与T为树矛盾.定理16.3无向图G具有生成树当且仅当G连通.生成树存在条件推论1G为n阶m条边的无向连通图，则mn1.证必要性显然.充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）11基本回路系统定理16.4设T为G的生成树，e为T的任意一条弦，则Te中含一个只有一条弦其余边均为T的树枝的圈.不同的弦对应的圈也不同.证设e=(u,v)，在T中u到v有惟一路径，则e为所求的圈.定义16.3设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,

7、…,emn+1为T的弦.设Cr为T添加弦er产生的只含弦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).求基本回路的算法：设弦e=(u,v)，先求T中u到v的路径uv，再并上弦e，即得对应e的基本回路.12基本割集的存在定理16.5设T是连通图G的一棵生成树，e为T的树枝，则G中存在只含树枝e，其余边都是弦的割集，且不同的树枝对应的割集也不同.证由定理16.1可知，e是T的

8、桥，因而Te有两个连通分支T1和T2，令Se={e

9、eE(G)且e的两个端点分别属于V(T1)和V(T2)}，由构造显然可知Se为G的割集，eSe且Se中除e外都是弦，所以Se为所求.显然不同的树枝对