第二节网络分析 网络——赋权图,记D=(V,E,C),其中C={c1,…,cn} c为边e:上的权(设c;≥0。 网络分析主要内容——最小部分树、最短路、最大流 2021/2/24
2021/2/24 第二节 网络分析 网络——赋权图，记D=（V，E，C），其中C={c1，…，cn}， ci为边ei上的权（设ci ）。 网络分析主要内容——最小部分树、最短路、最大流。 0
最小部分(支撑)树问题 问题:求网络D的部分树,使其权和最小 方法:避圈法( Kruskal,1956)、破圈法(管梅谷,1975) 例2求如图网络的最小部分树。 5 2021/2/24
2021/2/24 一. 最小部分（支撑）树问题 问题：求网络D的部分树，使其权和最小。 方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。 例 2 求如图网络的最小部分树。 v5 v1 v3 v6 v4 v2 v7 2 5 5 2 3 3 5 7 5 7 1 1
避圈法是一种选边的过程,其步骤如下: 1.从网络D中任选一点v,找出与ν相关联的 权最小的边[v,v,得第一个顶点v; 2.把顶点集V分为互补的两部分V,V,其中 j,与已选边相关联的点集 不与已选边相关联的点集; 3考虑所有这样的迦,”,]其中”,∈1”,∈V1,挑选 其中权最小的 4.重复3,直至全部顶点属于v1(即1=Φ) 2021/2/24
2021/2/24 避圈法是一种选边的过程，其步骤如下： 1. 从网络D中任选一点vi，找出与vi相关联的 权最小的边[vi，vj ]，得第二个顶点vj； 2. 把顶点集V分为互补的两部分V1 , V 1 ，其中 ，不与已选边相关联的点集； ，与已选边相关联的点集， 1 1 V V 其中权最小的； 考虑所有这样的边 其中 挑选 3. [ , ], , , 1 V 1 v v v V v 4. 重复3，直至全部顶点属于V 1 (即V 1 = )
用避圈法解例2 5 最小部分树如图上红线所示; 最小权和为14。 思考:破圈法是怎样做的呢? 见圈就破,去掉其中权最大的。 2021/2/24
2021/2/24 用避圈法解例2 v5 v1 v3 v6 v4 v2 v7 2 5 5 2 3 3 5 7 5 7 1 1 • 最小部分树如图上红线所示； 最小权和为14。 思考：破圈法是怎样做的呢？ ——见圈就破，去掉其中权最大的
最小部分树问题的应用例子 已知有A、B、C、D、E、F六个城镇间的道路网络 如图,现要在六个城镇间架设通讯网络(均沿道路架 设),每段道路上的架设费用如图。求能保证各城镇均 能通话且总架设费用最少的架设方案 E F B D
2021/2/24 最小部分树问题的应用例子 已知有A、B、C、D、E、F六个城镇间的道路网络 如图，现要在六个城镇间架设通讯网络（均沿道路架 设），每段道路上的架设费用如图。求能保证各城镇均 能通话且总架设费用最少的架设方案。 E A C B F D 5 10 6 9 3 5 3 9 8 7 2 8 4