离散数学课件-无向树

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,离散数学,李书杰,合肥工业大学,离散数学,1,学习内容,10.1 无向树,10.2 根树,2,3,如果将上图看作一个图的话，这个图就是一棵树，如下图。,4,定义10.2.1 无向树从无向图出发定义的树,无向树(树),:,连通而无回路的无向图，一般用T表示,叶,:树中度数为1的顶点,分支点/内部结点,:树中度数,1的顶点,森林,:,一个非连通图，如果其每个连通分支都是树，则称为森林,平凡树,:,平凡图，只有一个点且无边的图,右图为一棵12阶树.,声明:本章中所讨论的回路均,指简单回路或初级回路,5,无向树的性质,设,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,个连通分枝,G,1,G,k,(,k,1），,G,i,有,n,i,个结,点,m,i,条边，因为,G,i,连通无回路，所以有,m,i,=,n,i,-1，,n,=,n,1,+,n,2,+,n,k,m,=,m,1,+,m,2,+,m,k,=(,n,1,-1)+(,n,2,-1)+(,n,k,-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，,下面证明至少有一个结点,u,0,使deg(,u,0,)=1。,若不存在，则每个结点的度至少为2，所以2,n,2,m,，即,n,m,，这与,m,=,n,-1矛盾。,10,(3),(4)的证明,首先证明G中也无回路,删去,u,0,及其关联的边，得到含有,k,-1个结点的图,G,，,G,连通且,m,=,n,1。,由归纳假设知,G,无回路。,在,G,中加入,u,0,及其关联的边恢复到,G,，则,G,无回路。,再证明在G中任意两结点之间增加一条边，得到一条且仅有一条回路。,若在,G,中增加一条边(,u,i,u,j,)，,因为,G,连通，则在,G,中存在一条从,u,i,到,u,j,的路，,那么这条路与新加入的边(,u,i,u,j,)构成回路，,而且这个回路是唯一的。,若不唯一，删掉边(,u,i,u,j,)边,G,中必有回路，矛盾。,11,(4),(5)的证明,如果,G,中,无回路,但增加一条新边，得到一个且仅有一个包含新边的回路，则,G,连通且每条边均为桥。,证明 反证法。,假设,G,不连通，,则存在结点,u,i,与,u,j,，在,u,i,和,u,j,之间没有路，,所以增加边(,u,i,u,j,)不会产生回路，与已知矛盾。,由于,G,无回路，故删掉任意条边,e,都使,G,-e为非连通，,所以,G,中每条边都是桥。,12,(5),(6)的证明,如果,G,连通且每条边均为桥，则,G,中任意两个结点之间存在惟一的路径。,证明 由G是连通的可知，任意两个结点间有一条路，,若存在两点它们之间有多于一条的路，,则G中必有回路，,删去该回路上任一边，,图仍是连通的，,与G中每条边都是桥矛盾。,13,(6)(1)的证明,如果,G,中任意两个结点之间存在惟一的路径，则,G,是无回路的连通图。,证明 因为任意两结点间有唯一条路，则图,G,必连通。,若,G,有回路，,则在回路上任意两结点间有两条路，,与已知矛盾。,14,设,T,是,n,阶非平凡的无向树，则,T,中至少有两片树叶.,证 设,T,有,x,片树叶，m条边。由握手定理及定理10.2.1可知，,由上式解出,x,2.,无向树的性质(续),15,例题,例1 已知无向树,T,中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.试求树叶数,并画出满足要求的非同构的无向树.,解 用树的性质,m,=,n,1和握手定理.,设有,x,片树叶，于是,n,=1+2+,x,=3+,x,2,m,=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.由握手定理得,2,m,=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,生成树,设,G,为无向连通图，,若,G,的生成子图（,v=v,）是一棵树,则称这棵树为,G,的,生成树；,设,G,的一棵生成树为,T,则,T,中的边称为,T,的,树枝,在,G,中而不在,T,中的边称为,T,的,弦,所有弦的集合称为,生成树,T,的补,注意：,生成树,T,的补,不一定连通,也不一定不含回路,.,右图黑边构成生成树,红边构成补,定义10.2.2,18,生成树,若图,G,的生成子图是一棵树，则该树称为,G,的生成树。,生成树,T,的,树枝,:,G,在,T,中的边,生成树,T,的,弦,:,G,不在,T,中的边,生成树,T,的,补,（或,余树）,:所有弦的集合的导出子图,注意：,不一定连通,也不一定不含回路.,19,举例,例,如下图，,T,=,e,1,e,6,e,7,e,4,e,3,，,黑线表示生成树，红线构成树的补。,=,e,2,e,5,e,8,余树是非连通的，无回路,余树是非连通的，有回路,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,v,-1的图都不是树,（1）,T,的补的边数为9-5=4，所以不可能是树。,（2）,T,的补的边数为12-5=7，也不可能是树。,（3）有两种情况：,T,的补是生成树；,T,的补不连通且含圈。,21,生成树的存在性,无向图,G,具有生成树当且仅当,G,连通。,证明,必要性,，显然。,充分性,（破圈法）。,若,G,中无回路，,G,为自己的生成树。,若,G,中含回路，任取一回路，随意地删除回路上的一条边，,若再有回路再删除回路上的一条边，直到最后无回路为止。,易知所得图无回路、连通且为G的生成子图，,所以为,G,的生成树。,22,求连通图G=的生成树的算法,1 破圈法,2 避圈法,3 广度优先搜索算法,23,举例（破圈法）,删除边1,删除边3,删除边6,生成树不是唯一的！,24,最小生成树,对无向图或有向图的每一条边,e,附加一个实数,w,(,e,),称作,边,e,的权,.图连同附加在边上的权称作,赋权图,记作,G,=.,设,G,是,G,的子图,G,所有边的权的和称作,G,的权,记作,W,(,G,).,最小生成树,:赋权图的权最小的生成树,求最小生成树的算法,避圈法(,克鲁斯卡尔/,Kruskal算法,),设,G,=,将非环边按权从小到大排序：,e,1,e,2,e,m,.,(1)把,e,1,加入,T,中,(2)检查,e,2,若,e,2,与,e,1,不构成回路,则将,e,2,加入,T,中,否则弃去,e,2,.,(3)检查,e,3,重复进行直至得到生成树为止.,25,实例,例 求图的一棵最小生成树,W,(,T,)=38,26,1,2,3,4,4,5,6,7,7,8,1,2,3,4,4,5,6,7,7,8,27,普里姆(Prim)算法,普里姆算法的基本思想：,从连通图,G,=,V,E,中的某一顶点,u,0,出,发，选择与它关联的具有最小权值的边,(,u,0,v,),，,将其顶点加入到,生成树的顶点集合,U,中。以后每,一步从,一个顶点在,U,中,，而,另一个顶点不在,U,中,的各条边中选择,权值最小的边,(,u,v,),把它的顶点,加入到,集合,U,中。如此继续下去，直到网络中的,所有顶点都加入到生成树顶点集合,U,中为止。,28,用普里姆(Prim)算法构造最小生成树的过程,1,2,3,4,6,5,5,6,5,1,7,3,2,5,4,6,1,2,3,4,6,5,5,1,3,2,4,从节点开始，选最小权值的边,1,，节点（，,）入,U;,从,U,中选最小权值边,5,，且对应节点不在,U,中，入,U;,从,U,中选最小权值边,3,，且对应节点不在,U,中，,入,U;,从,U,中选最小权值边,4,，且对应节点不在,U,中，,入,U;,从,U,中选最小权值边,2,，且对应节点不在,U,中，,入,U;,29,