关键：不构成圈求支撑树的避圈法例：用避圈法求下图的生成树：深探法广探法
例：用避圈法求下图的生成树： 深探法 广探法 求支撑树的避圈法 关键：不构成圈
2.3最小支撑树问题赋权图(网络）：给图G=(V,E)，对G中的每一条边[v，v],相应地有一个数w，则称这样的图为赋权图，w,称为边[v,v]上的权。支撑树的权:若T=(V,E’）是G的一个支撑树E’中的所有边的权之和称为支撑树的权，记为W(T):Zw(T) =Wij[vi,v,leT定义：最小支撑树（最小树）T*：w(T*) = min w(T)
2.3 最小支撑树问题 赋权图(网络）: 给图G=(V,E), 对G中的每一条 边[vi , vj], 相应地有一个数wij, 则称这样的图为 赋权图, wij称为边[vi , vj]上的权. 支撑树的权:若T=(V,E’) 是G的一个支撑树, E’中的所有边的权之和称为支撑树的权, 记为 w(T): 定义: 最小支撑树(最小树)T* : v v T ij i j w T w [ , ] ( ) ( ) min ( ) * w T w T T
最小生成树一避圈法方法1步骤：中1）从图中任选一点，让VEV,图中其余点均包含在V2）从V与V的连线中找出一条最小边（若最小边有两条是相等，则任取其一），则这最小边一定包含在最小部分树内，并标注该边为虚线（或其它有显著标志即可）3）重复第2）步骤，直到所有点包含在V中为止
步骤： 1）从图中任选一点,让vi ∈V,图中其余点均包含在V’中 2）从V与V’的连线中找出一条最小边（若最小边有两 条是相等，则任取其一）,则这最小边一定包含在最小部 分树内，并标注该边为虚线（或其它有显著标志即可） 3）重复第2）步骤，直到所有点包含在V中为止。 最小生成树—避圈法方法1
避圈法方法1例题：公园路径系统如下图，S为入口，T为出口，A、B、......E为5个景点，现安安装电话线连接到各景点，则最小线路安装是什么？图：公园各景观间的最小电话线路安装
例题：公园路径系统如下图，S为入口，T为出口，A 、B、.、E为5个景点，现安安装电话线连接到各 景点，则最小线路安装是什么？ 避圈法方法1
避圈法方法21去掉G中所有边，得到n个孤立点；然后加边加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通（即:n-1条边)。V378VV5185236V42256
避圈法方法2: 去掉G中所有边，得到n个孤立点；然后加边。 加边的原则为：从最短边开始添加，加边的过程 中不能形成圈，直到点点连通(即:n-1条边)。 5 v1 v2 v3 v4 v5 v6 8 4 3 7 5 2 6 8 1