《离散数学课件-无向树》由会员分享，可在线阅读，更多相关《离散数学课件-无向树（29页珍藏版）》请在金锄头文库上搜索。
1、离散数学李书杰 合肥工业大学 离散数学1（2）G中无回路且m=n1; （3）G是连通的且m=n1; （4）G中没有回路, 但在任何两个不同的顶点之间加一条新 边,就会得到一条唯一的基本回路. （5）G是连通的且G中任何边均为桥; （6） G中任意两个顶点之间存在惟一的 一条基本通路。6(1)(2)的证明如果G是无回路的连通图，则G中无回路且m=n1，其中m是 边数，n是结点数证明 归纳法。当n=2时，因为G连通无回路，所以只有m=1，故m=n-1成立。假设n=k-1时命题成立，当n=k时，因G是无回路且连通，则至少有一个度为1的结点u，设与其关联的边为(u,w)，删去u，得到一个k-1个结点的
2、连通无向图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=n1，其中m是边数，n是结点数，则连 通且m=n1; 只须证明G是连通的。 证明 设G有k个连通分枝G1,Gk(k1），Gi有ni个结 点,mi条边，因为Gi连通无回路，所以有mi =ni-1，n=n1+n2+nkm=m1+m2+mk=(n1-1)+(n2-1)+(nk-1)=n-k 因为m=n-1，所以k=1，故G是连通的
3、。9(3)(4)的证明如果G连通且m=n1，则G中无回路, 但增加一条新边，得到 一个且仅有一个包含新边的回路。 证明 归纳法。 当n=2时，m=n-1=1，必无回路，如果增加一边得到且仅得 到一个回路。 设n=k-1时命题成立。考察n=k时的情况。 因为G是连通的，所以每个结点u有deg(u)1， 下面证明至少有一个结点u0使deg(u0)=1。 若不存在，则每个结点的度至少为2，所以2n2m，即n m ，这与m=n-1矛盾。10(3)(4)的证明首先证明G中也无回路 删去u0及其关联的边，得到含有k-1个结点的图G，G连通且m=n1。由归纳假设知G无回路。 在G中加入u0及其关联的边恢复到
4、G，则G无回路。 再证明在G中任意两结点之间增加一条边，得到一条且仅有一条回路。 若在G中增加一条边(ui,uj)， 因为G连通，则在G中存在一条从ui到uj的路， 那么这条路与新加入的边(ui,uj)构成回路， 而且这个回路是唯一的。 若不唯一，删掉边(ui,uj)边,G中必有回路，矛盾。11(4) (5)的证明如果G中无回路, 但增加一条新边，得到一个且仅有一个包含 新边的回路，则G连通且每条边均为桥。 证明 反证法。 假设G不连通， 则存在结点ui与uj，在ui和uj之间没有路， 所以增加边(ui,uj)不会产生回路，与已知矛盾。 由于G无回路，故删掉任意条边e都使G-e为非连通， 所以
5、G中每条边都是桥。12(5) (6)的证明如果G连通且每条边均为桥，则G中任意两个结点之间存在 惟一的路径。 证明 由G是连通的可知，任意两个结点间有一条路， 若存在两点它们之间有多于一条的路， 则G中必有回路， 删去该回路上任一边， 图仍是连通的， 与G中每条边都是桥矛盾。13(6) (1)的证明如果G中任意两个结点之间存在惟一的路径，则G是无回路 的连通图。 证明 因为任意两结点间有唯一条路，则图G必连通。 若G有回路， 则在回路上任意两结点间有两条路， 与已知矛盾。14定理10.2.2 设T 是n阶非平凡的无向树，则T中至少有两片树叶. 证 设T有x片树叶，m条边。由握手定理及定理10.
6、2.1可知 ，由上式解出x2.无向树的性质(续)15例题例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全 是树叶. 试求树叶数, 并画出满足要求的非同构的无向树. 解 用树的性质m=n1和握手定理. 设有x片树叶，于是 n=1+2+x=3+x,2m=2(n1)=2(2+x)=13+22+x 解出x=3，故T有3片树叶.T的度数列为1, 1, 1, 2, 2, 3有2棵非同构的无向树, 如图所示16例题例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的 度数均为4. 求T的阶数n. 解 设T的阶数为n, 则边数为n1, 4度顶点的个数为n7. 由握 手定理得2
7、m=2(n1)=51+21+31+4(n7) 解出n=8, 4度顶点为1个. T的度数列为1,1,1,1,1,2,3,417p生成树p设G为无向连通图，若G的生成子图（v=v）是一棵树, 则称这棵树为G的生成树；p设G的一棵生成树为T,则T中的边称为T的树枝,在G中而 不在T中的边称为T的弦,p所有弦的集合称为生成树T的补 p注意：生成树T的补不一定连通, 也不一定不含回路 . p右图黑边构成生成树p红边构成补定义10.2.2 18生成树定义10.2.2 若图G的生成子图是一棵树，则该树称为 G的生成树。生成树T的树枝: G在T中的边生成树T的弦: G不在T中的边 生成树T的补 （或余树）:
8、所有弦的集合的导出子图注意： 不一定连通, 也不一定不含回路. 19举例例 如下图，T=e1,e6,e7,e4,e3，黑线表示生成树，红线构成树的补。=e2,e5,e8余树是非连通的，无回路余树是非连通的，有回路20举例例 设T是6阶无向简单图G的一棵生成树，讨论下面的问 题： (1) 当G的边数e=9时，T的补是G的生成树吗？ (2) 当G的边数e=12时，T的补是G的生成树吗？ (3) 当G的边数e=10时，T的补可能有哪几种情况？ 解 对于树T，e=v-1，而任何ev或e的生成树的算法n1 破圈法n2 避圈法n3 广度优先搜索算法23举例（破圈法）删除边1删除边3删除边6生成树不是唯一的
9、！24最小生成树 对无向图或有向图的每一条边e附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作赋权图, 记作G=. 设G是G的子图, G所有边的权的和称作G的权, 记作W(G).最小生成树: 赋权图的权最小的生成树求最小生成树的算法避圈法 (克鲁斯卡尔/Kruskal算法) 设G=, 将非环边按权从小到大排序：e1, e2, , em. (1) 把e1加入T中 (2) 检查e2, 若e2与e1不构成回路, 则将e2加入T中, 否则弃去e2. (3) 检查e3, 重复进行直至得到生成树为止. 25实例例 求图的一棵最小生成树 W(T)=382612344567781234456
10、77827普里姆普里姆(Prim)(Prim)算法算法普里姆算法的基本思想：普里姆算法的基本思想：从连通图从连通图 G G = = V V, , E E 中的某一顶点中的某一顶点 u u0 0 出出 发，选择与它关联的具有最小权值的边发，选择与它关联的具有最小权值的边( (u u0 0, , v v) )， 将其顶点加入到将其顶点加入到生成树的顶点集合生成树的顶点集合U U中。以后每中。以后每 一步从一步从一个顶点在一个顶点在U U中中，而，而另一个顶点不在另一个顶点不在U U中中 的各条边中选择的各条边中选择权值最小的边权值最小的边( (u u, , v v) ), ,把它的顶点把它的顶点 加入到加入到集合集合U U中。如此继续下去，直到网络中的中。如此继续下去，直到网络中的 所有顶点都加入到生成树顶点集合所有顶点都加入到生成树顶点集合U U中为止。中为止。28用普里姆用普里姆(Prim)(Prim)算法构造最小生成树的过程算法构造最小生成树的过程1234655651 732 5461234655132 4从节点开始，选最小权值的边1，节点（，）入U; 从U中选最小权值边5，且对应节点不在U中，入U; 从U中选最小权值边3，且对应节点不在U中， 入U; 从U中选最小权值边4，且对应节点不在U中， 入U; 从U中选最小权值边2，且对应节点不在U中， 入U;29
