离散数学-无向树

1、离散数学-无向树1离散数学离散数学李书杰李书杰 合肥工业大学合肥工业大学离散数学离散数学离散数学-无向树2& 学习内容学习内容离散数学-无向树3离散数学-无向树4如果将上图看作一个图的话，这个图就是一棵树，如下图。如果将上图看作一个图的话，这个图就是一棵树，如下图。离散数学-无向树5定义定义10.2.1 10.2.1 无向树从无向图出发定义的树无向树从无向图出发定义的树n无向树无向树(树树): 连通而无回路的无向图，一般用连通而无回路的无向图，一般用T表示表示n叶叶: 树中度数为树中度数为1的顶点的顶点n分支点分支点/内部结点内部结点: 树中度数树中度数1的顶点的顶点n森林森林: 一个

2、非连通图，如果其每个连通分支都是树，则称为一个非连通图，如果其每个连通分支都是树，则称为森林森林n平凡树平凡树: 平凡图，只有一个点且无边的图平凡图，只有一个点且无边的图n右图为一棵右图为一棵12阶树阶树.n声明声明:本章中所讨论的回路均本章中所讨论的回路均n 指简单回路或初级回路指简单回路或初级回路 离散数学-无向树6无向树的性质无向树的性质定理定理10.2.1 设设G=是是n阶阶m条边的无向图，则下面各命题条边的无向图，则下面各命题是等价的：是等价的：（1）G是树是树(连通无回路连通无回路);（2）G中无回路且中无回路且m=n 1;（3）G是连通的且是连通的且m=n 1;（4）G中没有回路

3、中没有回路, 但在任何两个不同的顶点之间加一条新但在任何两个不同的顶点之间加一条新边边,就会得到一条唯一的基本回路就会得到一条唯一的基本回路.（5）G是连通的且是连通的且G中任何边均为桥中任何边均为桥;（6） G中任意两个顶点之间存在惟一的中任意两个顶点之间存在惟一的 一条基本通路。一条基本通路。离散数学-无向树7(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)，删

4、去u，得到一个k-1个结点的连通无向图G，离散数学-无向树8(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成立。离散数学-无向树9(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+nk m=m1+m2+mk=(n1-1)+(n2-1)+(nk

5、-1)=n-k因为m=n-1，所以k=1，故G是连通的。离散数学-无向树10(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矛盾。离散数学-无向树11(3)(4)的证明首先证明G中也无回路删去u0及其关联的边，得到含有k-1个结点的图G， G连

6、通且m=n1。由归纳假设知G无回路。在G中加入u0及其关联的边恢复到G，则G无回路。再证明在G中任意两结点之间增加一条边，得到一条且仅有一条回路。若在G中增加一条边(ui,uj)，因为G连通，则在G中存在一条从ui到uj的路，那么这条路与新加入的边(ui,uj)构成回路，而且这个回路是唯一的。若不唯一，删掉边(ui,uj)边,G中必有回路，矛盾。离散数学-无向树12(4) (5)的证明如果G中无回路, 但增加一条新边，得到一个且仅有一个包含新边的回路，则G连通且每条边均为桥。证明 反证法。假设G不连通，则存在结点ui与uj，在ui和uj之间没有路，所以增加边(ui,uj)不会产生回路，与已知矛

7、盾。由于G无回路，故删掉任意条边e都使G-e为非连通，所以G中每条边都是桥。离散数学-无向树13(5) (6)的证明如果G连通且每条边均为桥，则G中任意两个结点之间存在惟一的路径。证明 由G是连通的可知，任意两个结点间有一条路，若存在两点它们之间有多于一条的路，则G中必有回路，删去该回路上任一边，图仍是连通的，与G中每条边都是桥矛盾。离散数学-无向树14(6) (1)的证明如果G中任意两个结点之间存在惟一的路径，则G是无回路的连通图。证明 因为任意两结点间有唯一条路，则图G必连通。若G有回路，则在回路上任意两结点间有两条路，与已知矛盾。离散数学-无向树15定理定理10.2.210.2.2 设设

8、T T 是是n n阶非平凡的无向树，则阶非平凡的无向树，则T T中至少有两片树叶中至少有两片树叶. . 证证 设设T T有有x x片树叶，片树叶，m m条边。由握手定理及定理条边。由握手定理及定理10.2.110.2.1可知，可知， 由上式解出由上式解出x x 2.2.无向树的性质无向树的性质( (续续) ) 12( )2()imnmd vxnx离散数学-无向树16例题例题例例1 已知无向树已知无向树T中中, 有有1个个3度顶点度顶点, 2个个2度顶点度顶点, 其余顶点全其余顶点全是树叶是树叶. 试求树叶数试求树叶数, 并画出满足要求的非同构的无向树并画出满足要求的非同构的无向树. 解解 用树

9、的性质用树的性质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棵非同构的无向树棵非同构的无向树, 如图所示如图所示离散数学-无向树17例题例题例例2 已知无向树已知无向树T有有5片树叶片树叶, 2度与度与3度顶点各度顶点各1个个, 其余顶点其余顶点的度数均为的度数均为4. 求求T的阶数的阶数n. 解解 设设T的阶数为的阶数为n, 则边数为则边数为n 1, 4度顶点的个数为度顶点的个数为

10、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 离散数学-无向树18p生成树生成树p设设G G为无向连通图，为无向连通图，若若G G的生成子图（的生成子图（v=vv=v）是一棵树）是一棵树, ,则称这棵树为则称这棵树为G G的的生成树；生成树；p设设G G的一棵生成树为的一棵生成树为T,T,则则T T中的边称为中的边称为T T的的树枝树枝, ,在在G G中而中而不在不在T T中的边称为中的边称为T T的的弦弦, ,p所有弦的集合称为所有弦的集合称为生成

11、树生成树T T的补的补 p注意：注意：生成树生成树T T的补的补不一定连通不一定连通, , 也不一定不含回路也不一定不含回路. . p右图黑边构成生成树右图黑边构成生成树p红边构成补红边构成补定义定义10.2.2 10.2.2 T离散数学-无向树19生成树生成树定义定义10.2.2 若图若图G的生成子图是一棵树，则该树称为的生成子图是一棵树，则该树称为G的生成树。的生成树。生成树生成树T的的树枝树枝: G在在T中的边中的边生成树生成树T的的弦弦: G不在不在T中的边中的边T生成树生成树T的的补补 （或（或余树）余树）: 所有弦的集合的导出子图所有弦的集合的导出子图T注意：注意： 不一定连通不一

12、定连通, 也不一定不含回路也不一定不含回路. 离散数学-无向树20举例举例例例 如下图，如下图，T=e1,e6,e7,e4,e3，黑线表示生成树，红线构成树的补。黑线表示生成树，红线构成树的补。T=e2,e5,e8余树是非连通的，无回路余树是非连通的，无回路余树是非连通的，有回路余树是非连通的，有回路离散数学-无向树21举例举例例例 设设T是是6阶无向简单图阶无向简单图G的一棵生成树，讨论下面的问的一棵生成树，讨论下面的问题：题：(1) 当当G的边数的边数e=9时，时，T的补是的补是G的生成树吗？的生成树吗？(2) 当当G的边数的边数e=12时，时，T的补是的补是G的生成树吗？的生成树吗？(3

13、) 当当G的边数的边数e=10时，时，T的补可能有哪几种情况？的补可能有哪几种情况？解解 对于树对于树T，e=v-1，而任何，而任何ev或或ev-1的图都不是树的图都不是树（1）T的补的边数为的补的边数为9-5=4，所以不可能是树。，所以不可能是树。（2） T的补的边数为的补的边数为12-5=7，也不可能是树。，也不可能是树。（3）有两种情况：）有两种情况：T的补是生成树；的补是生成树； T的补不连通且含圈。的补不连通且含圈。离散数学-无向树22生成树的存在性生成树的存在性 n定理定理10.2.3 无向图无向图G具有生成树当且仅当具有生成树当且仅当G连通。连通。n证明证明 必要性必要性，显然。

14、，显然。n充分性充分性（破圈法）。（破圈法）。n 若若G中无回路，中无回路，G为自己的生成树。为自己的生成树。n 若若G中含回路，任取一回路，随意地删除回路上的一条边，中含回路，任取一回路，随意地删除回路上的一条边，n若再有回路再删除回路上的一条边，直到最后无回路为止。若再有回路再删除回路上的一条边，直到最后无回路为止。n易知所得图无回路、连通且为易知所得图无回路、连通且为G的生成子图，的生成子图，n所以为所以为G的生成树。的生成树。离散数学-无向树23求连通图G=的生成树的算法n1 破圈法n2 避圈法n3 广度优先搜索算法离散数学-无向树24举例（破圈法）删除边删除边1删除边删除边3删除边删

15、除边6生成树不是唯一的！离散数学-无向树25最小生成树最小生成树 对无向图或有向图的每一条边对无向图或有向图的每一条边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, 重复进行直至得到生成树为止重复进行直至得到生成树为止. 离