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

离散数学第十章树主要内容无向树及其性质生成树●根树及其应用离散数学1离散数学10.1无向树及其性质定义101连通无回路的无向图称为无向树,简称树每个连通分支都是树的无向图称为森林.平凡图称为平凡树.在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支点例星形树离散数学2离散数学无向树的性质定理101设G=<VE>是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,G2·nk,由归纳假设得m=n-1,=1,2.于是,m=m1+m2+1=n1+n2-2+1=n-13)→(4).只需证明G连通用反证法.否则G有(s≥2)个连通分支,它们都是树.于是,有m=m-1∑m=∑n-s=n-S(s≥2)这与m=n-1矛盾离散数学4离散数学证明(4)→(5).只需证明G中每条边都是桥.下述命题显然成立:G是n阶m条边的无向连通图,则m≥n-1ve∈E,G-e只有n-2条边,由命题可知Ge不连通,故e为桥.(5)→(6).由5易知G为树.由(1)=(2)知,Va,v∈V(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离散数学第十章树主要内容无向树及其性质生成树●根树及其应用离散数学31离散数学10.1无向树及其性质定义101连通无回路的无向图称为无向树,简称树每个连通分支都是树的无向图称为森林.平凡图称为平凡树.在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支点例星形树离散数学32离散数学无向树的性质定理101设G=<VE>是m阶m条边的无向图,则下面各命题是等价的:(1)G是树(2)G中任意两个顶点之间存在惟一的路径(3)G中无回路且m=n-1(4)G是连通的且m=n-1.(5)G是连通的且G中任何边均为桥.(6)G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.离散数学33离散数学证明证(1)→(2).若路径不惟一,必有回路.(2)→(3.若G中有回路,则回路上任意两点之间的路径不惟一对n用归纳法证明m=n-1当n=1时成立.设ns时成立,证n=k+1时也成立:任取一条边e,Ge有且仅有两个连通分支G1,G2·nk,由归纳假设得m=n-1,=1,2.于是,m=m1+m2+1=n1+n2-2+1=n-13)→(4).只需证明G连通用反证法.否则G有(s≥2)个连通分支,它们都是树.于是,有m=m-1∑m=∑n-s=n-S(s≥2)这与m=n-1矛盾离散数学34离散数学证明(4)→(5).只需证明G中每条边都是桥.下述命题显然成立:G是n阶m条边的无向连通图,则m≥n-1ve∈E,G-e只有n-2条边,由命题可知Ge不连通,故e为桥.(5)→(6).由5易知G为树.由(1)=(2)知,Va,v∈V(up),u到v有惟一路径,加新边(u,)得惟一的一个圈(6)→(1).只需证明G连通,这是显然的离散数学35离散数学屈婉玲第十章课件36离散数学屈婉玲第十章课件37离散数学屈婉玲第十章课件38离散数学屈婉玲第十章课件39离散数学屈婉玲第十章课件40离散数学屈婉玲第十章课件41离散数学屈婉玲第十章课件42离散数学屈婉玲第十章课件43离散数学屈婉玲第十章课件44离散数学屈婉玲第十章课件45离散数学屈婉玲第十章课件46离散数学屈婉玲第十章课件47离散数学屈婉玲第十章课件48离散数学屈婉玲第十章课件49离散数学屈婉玲第十章课件50离散数学屈婉玲第十章课件51离散数学屈婉玲第十章课件52离散数学屈婉玲第十章