离散数学第六章.ppt

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

1、第六章树§6.1树的定义定义6.1.1：连通无回路的图称为树。让我们来看一下《数据结构》中的树的定义：一棵树是一个或多个顶点的有限集合T，使得，⑴有一个特殊标识的顶点，称为根；⑵除根以外的其余顶点形成n≥0个划分，T1，T2，…，Tn，它们也都是树，称为根的子树。这里的树的定义更为一般。《数据结构》中树的定义与此定义的区别只是指定了一个特殊的顶点——根，并由此使得顶点之间形成了层次结构，而它同样也是一个无回路的连通图。7/27/20212离散数学树的举例bcdea树G：取a为根：abcde取b为根：badce取d为根：dbeac取e为根：edbac显然它们是同构的。数据结构中的树指定了一

2、个特殊的顶点为根。7/27/20213离散数学树的应用举例树的用途极其广泛，比如计算机网络中的最短通路、二叉树排序，各种层次结构的表示、等等。可以说，在计算机领域中几乎处处可以见到她的婆娑身影。例如：右图就是用树表示的算术表达式：(a+b)*c–d/cab+c*de/–7/27/20214离散数学树中只有单通路定理6.1.1树T中任何两个顶点之间恰有一条通路。证明:(存在性)因为树是连通图，所以任意两点之间有通路。(唯一性)设u,v∈V(T),若u和v之间有两条不同的(u,v)通路P1,P2，于是必有边xy,xy∈E(P1),但xyE(P2),显然H=P1∪P2-xy是连通图，从而H

3、中存在(x,y)-通路Pxy.于是Pxy+xy是T中的一条回路，与树的定义相矛盾。所以定理得证。此定理的逆不一定成立。uxyvP1P2Pxy7/27/20215离散数学几种等价说法定理6.1.2设G(p,q)是一个图，于是，下列五种说法相互等价：G是树；(1)(2)G连通且q=p–1;(2)(3)G无回路且q=p–1;(3)(4)G无回路,但对任意的u,v∈V(G),若uvE(G),则G+uv中恰有一条回路；(4)(5)G连通，但对任意e∈E(G),G–e不连通。(5)(1)7/27/20216离散数学树是点比边多一的连通图证明：因G是树，所以G连通，下对p做归纳证明q=p–

4、1：(1)p=1时，显然q=p–1；(2)假设对顶点数少于p的树，结论成立；(3)对于p个顶点的树G，p2,取e=uv∈E(G),由定理6.1.1知，e是唯一的(u,v)––通路，于是，G–e不连通而且恰有两个连通分支G1(p1,q1)和G2(p2，q2),显然，p1

5、数是p,由(2)知q–k=p–1但已知q=p–1,因此必有k=0.这说明G本身就无回路。7/27/20218离散数学树若添条边就会有回路证明：设G有k个连通分支，由于G无回路，所以G的每个连通分支均是树，于是，kkqi=pi-1(i=1,…,k),q=qi=(pi-1)=p–ki=1i=1但已知q=p–1,故k=1。即G连通，从而G是树。对G的任意两个非邻接的顶点u,v，由定理6.1.1,有唯一的(u,v)––通路，从而G+uv也就有唯一的一条回路。7/27/20219离散数学树若减条边就会不连通证明：任取u,v∈V(G),若uv∈E(G),则u和v是连通的；若uvE(G),则有(

6、4)知，G+uv有唯一的回路C。由于G中无回路，所以，u,v必在回路C上，显然，C–uv是G的连通子图，从而G中含(u,v)–通路，即uv,故G是连通图。对任意e∈E(G),若G–e仍连通，则说明G中含有回路，此与(4)矛盾，故G–e不连通。7/27/202110离散数学少条边就会不连通的图是树只须证G中无回路。若G中含回路C，取e=xy∈E(C),则C–e仍连通，任取u,v∈V(G),因G连通，故G中有(u,v)––通路P。若P不含e，则u,v在G–e中仍连通；若P中含e，则P中的e可以用C–e中的(x,y)––通路代替，从而u,v在G–e中仍连通。总之，u与v在G–e中连通，此与(

7、5)矛盾。故G无回路，因此，G是树。7/27/202111离散数学P不含e：P含e：uCvxyPexyPGGCev少条边就不连通的图是树的证明图示u7/27/202112离散数学平凡树和森林只有一个顶点的图（平凡图）称为平凡树。具有多个连通分支，且每个连通分支都是树的图称为森林。7/27/202113离散数学树中至少有两个悬挂点定理6.1.3任何非平凡树G(p,q)中至少有两个顶点的度数为1（悬挂点）。证明：(反证)已知G中每个点的