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

文档介绍：)树(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,