离散数学课件-无向树.ppt

离散数学李书杰 合肥工业大学lisjhfut@离散数学1& 学习内容学习内容10.1 10.1 无向树无向树无向树无向树10.2 10.2 根树根树根树根树23如果将上图看作一个图的话，这个图就是一棵树，如下图如果将上图看作一个图的话，这个图就是一棵树，如下图4定义定义10.2.1 10.2.1 无向树－－从无向图出发定义的树无向树－－从无向图出发定义的树n无向树无向树(树树): ¨连通而无回路的无向图，一般用连通而无回路的无向图，一般用T＝＝表示表示n叶叶: 树中度数为树中度数为1的顶点的顶点n分支点分支点/内部结点内部结点: 树中度数树中度数>1的顶点的顶点n森林森林: ¨一一个个非非连连通通图图，，如如果果其其每每个个连连通通分分支支都都是是树树，，则则称称为为森林森林n平凡树平凡树: ¨平凡图，只有一个点且无边的图平凡图，只有一个点且无边的图n右图为一棵右图为一棵12阶树阶树.n声明声明:本章中所讨论的回路均本章中所讨论的回路均n 指简单回路或初级回路指简单回路或初级回路 5无向树的性质无向树的性质定定理理10.2.1 设设G=是是n阶阶m条条边边的的无无向向图图，，则则下下面面各各命命题题是等价的：是等价的：（（1））G是树是树(连通无回路连通无回路);（（2））G中无回路且中无回路且m=n 1;（（3））G是连通的且是连通的且m=n 1;（（4））G中中没没有有回回路路, 但但在在任任何何两两个个不不同同的的顶顶点点之之间间加加一一条条新新边边,就会得到一条唯一的基本回路就会得到一条唯一的基本回路.（（5））G是连通的且是连通的且G中任何边均为桥中任何边均为桥;（（6）） G中任意两个顶点之间存在惟一的中任意两个顶点之间存在惟一的 一条基本通路。

一条基本通路6(1)(2)的证明如果G是无回路的连通图，则G中无回路且m=n1，其中m是边数，n是结点数证明 归纳法当n=2时，因为G连通无回路，所以只有m=1，故m=n-1成立假设n=k-1时命题成立，当n=k时，因G是无回路且连通，则至少有一个度为1的结点u，设与其关联的边为(u,w)，删去u，得到一个k-1个结点的连通无向图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=n1，其中m是边数，n是结点数，则连通且m=n1;只须证明G是连通的证明 设G有k个连通分枝G1,…,Gk(k≥1），Gi有ni个结点,mi条边，因为Gi连通无回路，所以有 mi =ni-1，n=n1+n2+…+nk m=m1+m2+…+mk=(n1-1)+(n2-1)+…+(nk-1)=n-k因为m=n-1，所以k=1，故G是连通的9(3)(4)的证明如果G连通且m=n1，则G中无回路, 但增加一条新边，得到一个且仅有一个包含新边的回路。

证明 归纳法当n=2时，m=n-1=1，必无回路，如果增加一边得到且仅得到一个回路设n=k-1时命题成立考察n=k时的情况因为G是连通的，所以每个结点u有deg(u)≥1，下面证明至少有一个结点u0使deg(u0)=1若不存在，则每个结点的度至少为2，所以2n≥2m，即n ≥m，这与m=n-1矛盾10(3)(4)的证明首先证明G中也无回路删去u0及其关联的边，得到含有k-1个结点的图G’， G’连通且m’=n’1由归纳假设知G’无回路在G’中加入u0及其关联的边恢复到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为非连通，所以G中每条边都是桥。

12(5) (6)的证明如果G连通且每条边均为桥，则G中任意两个结点之间存在惟一的路径证明 由G是连通的可知，任意两个结点间有一条路，若存在两点它们之间有多于一条的路，则G中必有回路，删去该回路上任一边，图仍是连通的，与G中每条边都是桥矛盾13(6) (1)的证明如果G中任意两个结点之间存在惟一的路径，则G是无回路的连通图证明 因为任意两结点间有唯一条路，则图G必连通若G有回路，则在回路上任意两结点间有两条路，与已知矛盾14定理定理10.2.210.2.2 设设T T 是是n n阶非平凡的无向树，则阶非平凡的无向树，则T T中至少有两片树叶中至少有两片树叶. . 证证 设设T T有有x x片树叶，片树叶，m m条边由握手定理及定理条边由握手定理及定理10.2.110.2.1可知，可知， 由上式解出由上式解出x x 2.2.无向树的性质无向树的性质( (续续) ) 15例题例题例例1 已已知知无无向向树树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棵非同构的无向树棵非同构的无向树, 如图所示如图所示16例题例题例例2 已已知知无无向向树树T有有5片片树树叶叶, 2度度与与3度度顶顶点点各各1个个, 其其余余顶顶点点的度数均为的度数均为4. 求求T的阶数的阶数n. 解解 设设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 17p生成树生成树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所有弦的集合称为所有弦的集合称为生成树生成树T T的补的补 p注意：注意：生成树生成树T T的补的补不一定连通不一定连通, , 也不一定不含回路也不一定不含回路. . p右图黑边构成生成树右图黑边构成生成树p红边构成补红边构成补定义定义10.2.2 10.2.2 18生成树生成树定义定义10.2.2 若图若图G的生成子图是一棵树，则该树称为的生成子图是一棵树，则该树称为G的生成树。

的生成树生成树生成树T的的树枝树枝: G在在T中的边中的边生成树生成树T的的弦弦: G不在不在T中的边中的边生成树生成树T的的补补 （或（或余树）余树）: 所有弦的集合的导出子图所有弦的集合的导出子图注意：注意： 不一定连通不一定连通, 也不一定不含回路也不一定不含回路. 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，而任何，而任何e≥v或或e

所以不可能是树2）） T的补的边数为的补的边数为12-5=7，也不可能是树也不可能是树3）有两种情况：）有两种情况：T的补是生成树；的补是生成树； T的补不连通且含圈的补不连通且含圈21生成树的存在性生成树的存在性 n定理定理10.2.3 无向图无向图G具有生成树当且仅当具有生成树当且仅当G连通n证明证明 必要性必要性，显然n充分性充分性（破圈法）破圈法）n 若若G中无回路，中无回路，G为自己的生成树为自己的生成树n 若若G中含回路，任取一回路，随意地删除回路上的一条边，中含回路，任取一回路，随意地删除回路上的一条边，n若再有回路再删除回路上的一条边，直到最后无回路为止若再有回路再删除回路上的一条边，直到最后无回路为止n易知所得图无回路、连通且为易知所得图无回路、连通且为G的生成子图，的生成子图，n所以为所以为G的生成树的生成树22求连通图G=的生成树的算法n1 破圈法n2 避圈法n3 广度优先搜索算法23举例（破圈法）删除边删除边1删除边删除边3删除边删除边6生成树不是唯一的！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)=38261234456778123445677827普里姆普里姆(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)算法构造最小生成树的过程算法构造最小生成树的过程123465565173254612346551324•从节点①开始，选最小权值的边1，节点（①，③）入U;•从U中选最小权值边5，且对应节点不在U中，②入U;•从U中选最小权值边3，且对应节点不在U中， ⑤入U;•从U中选最小权值边4，且对应节点不在U中， ⑥入U;•从U中选最小权值边2，且对应节点不在U中， ④入U;29。