《离散数学》PPT课件

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

1、离散数学DiscreteMathematics9/15/20212:53AM1DiscreteMath.,huangliujia第十六章树§16.1无向树及其性质§16.2生成树§16.3根树及其应用9/15/20212:53AM2DiscreteMath.,huangliujia定义16.1无向树:连通无回路的无向图平凡树:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点:树中度数2的顶点16.1无向树及其性质右图为一棵12阶树.声明:本章中所讨论的回路均指简单回路

2、或初级回路9/15/20213DiscreteMath.,huangliujia无向树的性质定理16.1设G=是n阶m条边的无向图，则下列等价的：（1）G是树;（2）G中任意两个顶点之间存在惟一的路径;（3）G中无回路且m=n1;（4）G是连通的且m=n1;（5）G是连通的且G中任何边均为桥;（6）G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.证明：①②由于G是树，所以G是连通的，u,vV，u和v之间存在一条路。若路不惟一，设L1和L2都是

3、u和v之间的路，则由L1和L2上的边组成了G中的一个回路，矛盾。9/15/20214DiscreteMath.,huangliujia②③先证G中无回路。若G中存在某个结点v上的环，uV，由条件知u到v存在一条路L1：u…v，则u到v有另一条路L2：u…vv，矛盾。若G中存在长度大于等于2的一条回路，则回路上两个结点之间存在不同的路,矛盾。所以G中无回路。以下用归纳法证明m=n–1。当n=1时，G为平凡图，m=0=1–1=n–1。结论成立。设n≤k时，结论成立。下证n=k+1时，结论也成立。

4、设e=(u,v)是G中的一条边，由于G中无回路，所以G-e有两个连通分支G1和G2，设它们的结点数和边数分别为：n1，m1和n2，m2。于是有n1≤k和n2≤k，由归纳假设知：m1=n1–1和m2=n2-1，m=m1＋m2＋1=n1-1＋n2-1＋1=n-1。9/15/20215DiscreteMath.,huangliujia③④只须证明G是连通的。若不然,设G有s(s≥2)个连通分支G1,G2,…,Gs,Gi中均无回路，都是树。由①②③可知，mi=ni–1，i=1,…,s。于是m=m

5、1＋m2＋…＋ms=n1-1＋n2-1＋…＋ns-1=n1＋n2＋…＋ns-s=n–s，由于s≥2，这与m=n–1矛盾。所以G是连通图。④⑤只须证明G的每一条边均为桥。设e是G的任意边，删除e得子图G1，它的边数m1=m-1，结点数n1=n，m1=m–1=n-1-1=n-2=n1-2＜n1-1，由习题14的第49题知G1不是连通图，所以e是桥。⑤⑥由于G中每一条边均为桥，因而G中无回路。又因为G连通，所以G是树。由①②知，u,vV，u≠v，u与v之间存在一条惟一的路。在u与v之间增加一条

6、新边,得到G的一条回路,显然这条回路是惟一的。⑥①只须证明G是连通的，u,vV，u≠v，在u与v之间增加一条新边(u,v)就产生G的一个惟一的回路，故结点u和结点v连通。由于u与v是任意的，所以G是连通图。9/15/20216DiscreteMath.,huangliujia无向树的性质(续)定理16.2设T是n阶非平凡的无向树，则T中至少有两片树叶.由上式解出x2.证设T有x片树叶，由握手定理及定理9.1可知，9/15/20217DiscreteMath.,huangliujia例题例1

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

8、求的所有非同构的无向树.解设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棵非同构的无向树9/15/20219DiscreteMath.,huangliujia16.2生成树定义16.2设G为无向连通图G的生成树:G的生成子图并且是树生成树T的树枝:G在T中的边生成树T的弦:G不在T中的边注意：不一定连通,也不一定不含回路.生成树T的