下载此文档

最小生成树课件教学内容.ppt

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

1/34

下载提示

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

同意并开始全文预览

(约 1-6 秒)

1/34 下载此文档

文档列表 文档介绍

)树(tree):无向图例如,,但G3(有圈)和G4(不连通)则不是树。,则下述命题等价:1)G是树(G无圈且连通);2)G无圈,且有n-1条边;3)G连通,且有n-1条边;4)G无圈,但添加任一条新边恰好产生一个圈;5)G连通,且删去一条边就不连通了(即G为最最小连通图);6))图的生成树(或支撑树SpanningTree)定义若T是包含图G的全部顶点的子图,它又是树,=(V,E),一个图的生成树不唯一。例如,,(a)、(b)、(c)均是(d)的生成树。(c)(d)(a)(b)(II)找图中生成树的方法可分为两种:避圈法和破圈法A避圈法:,每步选出一条边使它与已选边不构成圈,直到选够n-“避圈法”或“加边法”在避圈法中,按照边的选法不同,找图中生成树的方法可分为两种:)深探法若这样的边的另一端均已有标号,就退到标号为步骤如下:i)在点集V中任取一点u,ii)若某点v已得标号,,则给w代v,重复ii).i-1的r点,以r代v,重复ii),=0查一端点为v的各边,另一w以标号i+1,)深探法图100123456789101112步骤如下:若这样的边的另一端均已有标号,就退到标号为i)在点集V中任取一点u,ii)若某点v已得标号,,则给w代v,重复ii).i-1的r点,以r代v,重复ii),,另一w以标号i+1,

最小生成树课件教学内容来自淘豆网www.taodocs.com转载请标明出处.