离散数学屈婉玲第十章课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,离散数学,第十章树,主要内容,无向树及其性质,生成树,根树及其应用,离散数学,1,离散数学,10.1无向树及其性质,定义101连通无回路的无向图称为无向树,简称树每个连,通分支都是树的无向图称为森林.平凡图称为平凡树.在无,向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为,分支点,例,星形树,离散数学,2,离散数学,无向树的性质,定理101设G=是m阶m条边的无向图,则下面各命题,是等价的:,(1)G是树,(2)G中任意两个顶点之间存在惟一的路径,(3)G中无回路且m=n-1,(4)G是连通的且m=n-1.,(5)G是连通的且G中任何边均为桥.,(6)G中没有回路,但在任何两个不同的顶点之间加一条新,边后所得图中有惟一的一个含新边的圈.,离散数学,3,离散数学,证明,证(1)(2).若路径不惟一,必有回路.,(2)(3.若G中有回路,则回路上任意两点之间的路径不,惟一对n用归纳法证明m=n-1,当n=1时成立.设ns时成立,证n=k+1时也成立:任取,一条边e,Ge有且仅有两个连通分支G1,G2nk,由归,纳假设得m=n-1,=1,2.于是,m=m1+m2+1=n1+n2-2+1=n-1,3)(4).只需证明G连通用反证法.否则G有(s2)个连通,分支,它们都是树.于是,有m=m-1,m=n-s=n-S(s2),这与m=n-1矛盾,离散数学,4,离散数学,证明,(4)(5).只需证明G中每条边都是桥.下述命题显然成立:G,是n阶m条边的无向连通图,则mn-1,veE,G-e只有n-2条边,由命题可知Ge不连通,故e为桥.,(5)(6).由5易知G为树.由(1)=(2)知,Va,vV(up),u到v有惟一路径,加新边(u,)得惟一的一个圈,(6)(1).只需证明G连通,这是显然的,离散数学,5,离散数学屈婉玲第十章课件,6,离散数学屈婉玲第十章课件,7,离散数学屈婉玲第十章课件,8,离散数学屈婉玲第十章课件,9,离散数学屈婉玲第十章课件,10,离散数学屈婉玲第十章课件,11,离散数学屈婉玲第十章课件,12,离散数学屈婉玲第十章课件,13,离散数学屈婉玲第十章课件,14,离散数学屈婉玲第十章课件,15,离散数学屈婉玲第十章课件,16,离散数学屈婉玲第十章课件,17,离散数学屈婉玲第十章课件,18,离散数学屈婉玲第十章课件,19,离散数学屈婉玲第十章课件,20,离散数学屈婉玲第十章课件,21,离散数学屈婉玲第十章课件,22,离散数学屈婉玲第十章课件,23,离散数学屈婉玲第十章课件,24,离散数学屈婉玲第十章课件,25,离散数学屈婉玲第十章课件,26,离散数学屈婉玲第十章课件,27,离散数学屈婉玲第十章课件,28,离散数学屈婉玲第十章课件,29,离散数学屈婉玲第十章课件,30,