离散数学课件-无向树

离散数学课件-无向树

ID:46908588

大小:1.04 MB

页数:29页

时间:2019-11-29

离散数学课件-无向树_第1页
离散数学课件-无向树_第2页
离散数学课件-无向树_第3页
离散数学课件-无向树_第4页
离散数学课件-无向树_第5页
资源描述:

《离散数学课件-无向树》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、离散数学李书杰合肥工业大学lisjhfut@hfut.edu.cn离散数学1学习内容10.1无向树10.2根树23如果将上图看作一个图的话,这个图就是一棵树,如下图。4定义10.2.1无向树--从无向图出发定义的树无向树(树):连通而无回路的无向图,一般用T=表示叶:树中度数为1的顶点分支点/内部结点:树中度数>1的顶点森林:一个非连通图,如果其每个连通分支都是树,则称为森林平凡树:平凡图,只有一个点且无边的图右图为一棵12阶树.声明:本章中所讨论的回路均指简单回路或初级回路5无向树的性质定理10.2.1设G=

2、是n阶m条边的无向图,则下面各命题是等价的:(1)G是树(连通无回路);(2)G中无回路且m=n1;(3)G是连通的且m=n1;(4)G中没有回路,但在任何两个不同的顶点之间加一条新边,就会得到一条唯一的基本回路.(5)G是连通的且G中任何边均为桥;(6)G中任意两个顶点之间存在惟一的一条基本通路。6(1)(2)的证明如果G是无回路的连通图,则G中无回路且m=n1,其中m是边数,n是结点数证明归纳法。当n=2时,因为G连通无回路,所以只有m=1,故m=n-1成立。假设n=k-1时命题成立,当n=k时,因G是无回路且连通,则

3、至少有一个度为1的结点u,设与其关联的边为(u,w),删去u,得到一个k-1个结点的连通无向图G’,7(1)(2)的证明(续)由归纳假设可知,G’的边数m’=n’-1=(k-1)-1=k-2。再将结点u及(u,w)放入原位,恢复到图G,那么G的边数m=m’+1=(k-2)+1=k-1,结点数n=n’+1=k,故m=n-1成立。8(2)(3)的证明如果G中无回路且m=n1,其中m是边数,n是结点数,则连通且m=n1;只须证明G是连通的。证明设G有k个连通分枝G1,…,Gk(k≥1),Gi有ni个结点,mi条边,因为Gi连通无

4、回路,所以有mi=ni-1,n=n1+n2+…+nkm=m1+m2+…+mk=(n1-1)+(n2-1)+…+(nk-1)=n-k因为m=n-1,所以k=1,故G是连通的。9(3)(4)的证明如果G连通且m=n1,则G中无回路,但增加一条新边,得到一个且仅有一个包含新边的回路。证明归纳法。当n=2时,m=n-1=1,必无回路,如果增加一边得到且仅得到一个回路。设n=k-1时命题成立。考察n=k时的情况。因为G是连通的,所以每个结点u有deg(u)≥1,下面证明至少有一个结点u0使deg(u0)=1。若不存在,则每个结点的度至少

5、为2,所以2n≥2m,即n≥m,这与m=n-1矛盾。10(3)(4)的证明首先证明G中也无回路删去u0及其关联的边,得到含有k-1个结点的图G’,G’连通且m’=n’1。由归纳假设知G’无回路。在G’中加入u0及其关联的边恢复到G,则G无回路。再证明在G中任意两结点之间增加一条边,得到一条且仅有一条回路。若在G中增加一条边(ui,uj),因为G连通,则在G中存在一条从ui到uj的路,那么这条路与新加入的边(ui,uj)构成回路,而且这个回路是唯一的。若不唯一,删掉边(ui,uj)边,G中必有回路,矛盾。11(4)(5)的证明

6、如果G中无回路,但增加一条新边,得到一个且仅有一个包含新边的回路,则G连通且每条边均为桥。证明反证法。假设G不连通,则存在结点ui与uj,在ui和uj之间没有路,所以增加边(ui,uj)不会产生回路,与已知矛盾。由于G无回路,故删掉任意条边e都使G-e为非连通,所以G中每条边都是桥。12(5)(6)的证明如果G连通且每条边均为桥,则G中任意两个结点之间存在惟一的路径。证明由G是连通的可知,任意两个结点间有一条路,若存在两点它们之间有多于一条的路,则G中必有回路,删去该回路上任一边,图仍是连通的,与G中每条边都是桥矛盾。13(6)

7、(1)的证明如果G中任意两个结点之间存在惟一的路径,则G是无回路的连通图。证明因为任意两结点间有唯一条路,则图G必连通。若G有回路,则在回路上任意两结点间有两条路,与已知矛盾。14定理10.2.2设T是n阶非平凡的无向树,则T中至少有两片树叶.证设T有x片树叶,m条边。由握手定理及定理10.2.1可知,由上式解出x2.无向树的性质(续)15例题例1已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.试求树叶数,并画出满足要求的非同构的无向树.解用树的性质m=n1和握手定理.设有x片树叶,于是n=1+2+x=3+x

8、,2m=2(n1)=2(2+x)=13+22+x解出x=3,故T有3片树叶.T的度数列为1,1,1,2,2,3有2棵非同构的无向树,如图所示16例题例2已知无向树T有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.求T的阶数n.解设T

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。