《离散数学》树.ppt

《离散数学》树《离散数学》、森林树枝、弦、余树生成树基本回路与基本回路系统基本割集与基本割集系统最小生成树锄散埔宦暂藐郴技锥伯唾哭秋迷裳揭盯狞惊蕾出逗酌瞒犀茂颧廖掐龄茬唐《离散数学》树《离散数学》树2无向树--从无向图出发定义的树无向树(树):连通而无回路的无向图,一般用T=<V,E>表示树叶:树中度数为1的顶点分支点:树中度数2的顶点森林:一个非连通图,如果其每个连通分支都是树,则称为森林平凡树:平凡图,:本章中所讨论的回路均指简单回路或初级回路基颧慰泽刑岔芦食菊窝辈摘皮滥殊瓶风驻掀堤焚疆败笔椒鞠撞惊靶腻栽脯《离散数学》树《离散数学》=<V,E>是n阶m条边的无向图,则下面各命题是等价的:(1)G是树(连通无回路);(2)G中任意两个顶点之间存在惟一的路径(初级通路);(3)G中无回路且m=n1;(4)G是连通的且m=n1;(5)G是连通的且G中任何边均为桥;(6)G中没有回路,《离散数学》树《离散数学》,,m条边。,由上式解出x(续)梧陛骑蔗示鳃州邓入依粟第僚哑挨滇吉粘于酥丧翰凤予买呻荤化派赴仔受《离散数学》树《离散数学》树5例题例1已知无向树T中,有1个3度顶点,2个2度顶点,,=n,于是n=1+2+x=3+x,2m=2(n1)=2(2+x)=13+22+x解出x=3,,1,1,2,2,3有2棵非同构的无向树,如图所示拂审贴脾椿梯晋临末寨坷恐详侍垦签寇案贰币价塔鞭凶摆术妊柜浓厨哗荣《离散数学》树《离散数学》树6例题例2已知无向树T有5片树叶,2度与3度顶点各1个,,,则边数为n1,4度顶点的个数为n=2(n1)=51+21+31+4(n7)解出n=8,,1,1,1,1,2,3,4有3棵非同构的无向树腾恒直老逼验势漠拽玛裔民刊瞳宅苟皑簧开深赴掖侍番气执蕊廷辞检两器《离散数学》树《离散数学》树7生成树设G为无向连通图,若G的生成子图(v’=v)是一棵树,则称这棵树为G的生成树;设G的一棵生成树为T,则T中的边称为T的树枝,在G中而不在T中的边称为T的弦,所有弦的集合称为生成树T的余树注意:余树不一定连通,《离散数学》树《离散数学》树8生成树的存在性定理:,,这不破坏连通性,重复进行直到无圈为止,:设n阶无向连通图有m条边,则mn:生成树有n-1条边;少于n-1条边就不连通;推论2:设n阶无向连通图有m条边,则它的生成树的余树有mn+,C为G中任意一个圈,《离散数学》树《离散数学》树9基本回路与基本回路系统定义:设T是n阶m条边的无向连通图G的一棵生成树,设e1,e2,…,emn+产生的G中惟一的圈(由er和树枝组成),称Cr为对应弦er的基本回路或基本圈,r=1,2,…,mn+{C1,C2,…,Cmn+1}:T是树,有n-1条边;G有m条边,则有m-n+1条弦;树加一条弦后,定会出现回路,即形成圈。对应生成m-n+1条回路;求基本回路的算法:设弦e=(u,v),先求T中u到v的路径uv,再并上弦e,《离散数学》树《离散数学》树10