下载此文档

9.1无向树及生成树.ppt

文档分类：IT计算机 | 页数：约29页举报非法文档有奖

1/29

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/29 下载此文档

文档列表 文档介绍

、森林树枝、弦、(树):连通而无回路的无向图,:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点:树中度数:=<V,E>是n阶m条边的无向图,则下面各命题是等价的:(1)G是树(连通无回路);(2)G中任意两个顶点之间存在惟一的路径;(3)G中无回路且m=n1;(4)G是连通的且m=n1;(5)G是连通的且G中任何边均为桥;(6)G中没有回路,(续),,,由上式解出x,有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棵非同构的无向树,,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,:G的生成子图并且是树生成树T的树枝:G在T中的边生成树T的弦:G不在T中的边生成树T的余树:所有弦的集合的导出子图注意:不一定连通,,,这不破坏连通性,重复进行直到无圈为止,,则mn,则它的生成树的余树有mn+,C为G中任意一个圈,,设e1,e2,…,emn+产生的G中惟一的圈(由er和树枝组成),称Cr为对应弦er的基本回路或基本圈,r=1,2,…,mn+{C1,C2,…,Cmn+1}:设弦e=(u,v),先求T中u到v的路径uv,再并上弦e,

9.1无向树及生成树来自淘豆网m.daumloan.com转载请标明出处.

9.1无向树及生成树.ppt

无向树及生成树