7-7 树与生成树

《7-7 树与生成树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树与生成树中国海洋大学计算机系主要内容无向树及其相关概念生成树基本回路与基本回路系统基本割集与基本割集系统最小生成树学习要点与基本要求实例分析无向树的定义定义7-7.1一个连通且无回路的无向图称为树。树叶：树中度数为1的结点；分枝点：度数大于1的结点森林：每个连通分支都是树的无向图。树的6个等价定义定理7-7.1给定图T，以下关于树的定义是等价的。（1）无回路的连通图;（2）无回路且e=v1，其中e是边数，v是结点数;（3）连通且e=v1;（4）无回路,但增加一条新边，得到一个且仅有一个包含新边的回路。（5）连通且每条边均为桥;（6）G中任意两个结点之间存在惟一的路径;Go(1)(2)

2、的证明如果T是无回路的连通图，则G中无回路且e=v1，其中e是边数，v是结点数证明归纳法。当v=2时，因为T连通无回路，所以只有e=1，故e=v-1成立。假设v=k-1时命题成立，当v=k时，因T是无回路且连通，则至少有一个度为1的结点u，设与其关联的边为(u,w)，删去u，得到一个k-1个结点的连通无向图T’，(1)(2)的证明（续）由归纳假设可知，T’的边数e’=v’-1=(k-1)-1=k-2。再将结点u及(u,w)放入原位，恢复到图T，那么T的边数e=e’+1=(k-2)+1=k-1，结点数v=v’+1=k，故e=v-1成立。return(2)(3)的证明如果T中无回路且e=v

3、1，其中e是边数，v是结点数，则连通且e=v1;只须证明T是连通的。证明设T有k个连通分枝T1,…,Tk(k≥2），Ti有vi个结点,ei条边，因为Ti连通无回路，所以有ei=vi-1，v=v1+v2+…+vke=e1+e2+…+ek=(v1-1)+(v2-1)+…+(vk-1)=v-k因为e=v-1，所以k=1，故T是连通的。return(3)(4)的证明如果T连通且e=v1，则T中无回路,但增加一条新边，得到一个且仅有一个包含新边的回路。证明归纳法。当v=2时，e=v-1=1，必无回路，如果增加一边得到且仅得到一个回路。设v=k-1时命题成立。考察v=k时的情况。因为T是连通的，

4、所以每个结点u有deg(u)≥1，下面证明至少有一个结点u0使deg(u0)=1。若不存在，则每个结点的度至少为2，所以2v≥2e，即v≥e，这与e=v-1矛盾。(3)(4)的证明删去u0及其关联的边，得到含有k-1个结点的图T’，T’连通且e’=v’1。由归纳假设知T’无回路。在T’中加入u0及其关联的边恢复到T，则T无回路。若在T中增加一条边(ui,uj)，因为T连通，则在T中存在一条从ui到uj的路，那么这条路与新加入的边(ui,uj)构成回路，而且这个回路是唯一的。若不唯一，删掉边(ui,uj)边,T中必有回路，矛盾。return(4)(5)的证明如果T中无回路,但增加一条新边

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

6、证明因为任意两结点间有唯一条路，则图T必连通。若T有回路，则在回路上任意两结点间有两条路，与已知矛盾。return无向树的性质定理7-7.2任一棵树中至少有两片树叶。证设T=是无向树，其中

7、V

8、=v，

9、E

10、=e设T有x片树叶，则剩余的v-x各结点的度均大于等于2，由握手定理及定理7-7.1可知，解上式可得x2.定理得证。关于无向树计算的实例例一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度结点，问T有几个结点。解设有n个结点，则5+3×2+(n-8)×3=2(n-1)得n=11实例例下面两个正整数序列中，哪个能充当无向树的度数序列？若能画出2棵非同构的无向树。（1）1

11、,1,1,1,2,3,3,4（2）1,1,1,1,2,2,3,3解（1）不可以，因为所有度数之和等于16，而结点数为8，假设可以构成树，则度数之和应为14，所以不可以。（2）可以。实例例设G为n（n≥5）阶简单图，证明G或G的补图中必含圈。证设简单图G和其补图的边数分别为m和m’，则m+m’=n(n-1)/2根据鸽巢原理，G与其补图必有一个边数≥n(n-1)/4，不妨设G的边数m≥n(n-1)/4，下面证G中