第二节网络分析 网络——赋权图,记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
二.最短路问题 1.问题:求网络D中一定点v到其它点的最短路。 例3求如图网络中η至v的最短路,图中数字 为两点间距离。 5 2.方法:标号法( Dijkstra,1959) 给每点v标号团d,v,其中d为v1至v的最短距,v为 最短路上的前一点 2021/2/24
2021/2/24 二. 最短路问题 1. 问题：求网络D中一定点v1到其它点的最短路。 例3 求如图网络中v1至v7的最短路，图中数字 为两点间距离。 v5 v1 v3 v6 v4 v2 v7 2 5 5 2 3 3 5 7 5 7 1 1 2. 方法：标号法（Dijkstra，1959） 给每点vj标号[dj，vi ]，其中dj为v1至vj的最短距，vi为 最短路上的前一点
标号法步骤: 1.给ν,标号O,v,] 已标号点集, 2把顶点集V分为互补的两部分 未标号点集 3.考虑所有这样的边]其中v,∈,∈EV 挑选其中与v距最短(mn+c)的进行标号 4重复3,直至终点(本例即v,)标上号d,,则 d即最短距,反向追踪可求出最短路。 2021/2/24
2021/2/24 标号法步骤： 即最短距，反向追踪可求出最短路。 重复 ，直至终点（本例即 ）标上号 ，则 挑选其中与 距最短（ 的 进行标号。 考虑所有这样的边 其中 未标号点集； 已标号点集， 把顶点集 分为互补的两部分 给 标号 ， 4 . 3 [ , ] ) 3 . [ , ], , , : : 2 . 1 . [0 ]; 7 7 7 1 1 1 1 1 1 1 d v d v v d c v v v v V v V V V V v v min +
用标号法解例3 其中2=min{0+20+5,0+3} [0 [8 [13,v6 7 4 5 [3,v] 其中3-mn{0+3,0+5,2+2,2+7} 最短距为13; 最短路为v 1-12-13-15-16-17 2021/2/24
2021/2/24 用标号法解例3 v5 v1 v3 v6 v4 v2 v7 2 5 5 2 3 3 5 7 5 7 1 1 [0，v1 ] [2，v1 ] [3，v1 ] 其中2=min{0+2,0+5,0+3} 其中3=min{0+3，0+5，2+2，2+7} [4，v2 ] [7，v3 ] [8，v5 ] [13，v6 ] 最短距为13； 最短路为v1 -v2 -v3 -v5 -v6 -v7
最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划 下面给出一辆新汽车的价格以及一辆汽车的使用 维修费用万元) 年号 价格 2.12.3242.6 汽车使用年龄0-11-22-33445 维修费用0.71.11.52 2.5 试用网络分析中求最短路的方法确定公司可采用 的最优策略。 方法:以年号作顶点绘图,连线表示连续使用期间,以 费用作路长
2021/2/24 最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划。 下面给出一辆新汽车的价格以及一辆汽车的使用 维修费用(万元)： 年号 1 2 3 4 5 价格 2 2.1 2.3 2.4 2.6 汽车使用年龄 0–1 1–2 2–3 3–4 4–5 维修费用 0.7 1.1 1.5 2 2.5 试用网络分析中求最短路的方法确定公司可采用 的最优策略。 方法：以年号作顶点绘图，连线表示连续使用期间，以 费用作路长
最大流问题 1.问题已知网络D=(V,A,C),其中V为顶点 集,A为弧集,C={G为容量集,cn为弧(v,v 上的容量。现D上要通过一个流},其中后为弧 (v,v)上的流量。问应如何安排流量可使D上 通过的总流量v最大? 例如: 2021/2/24
2021/2/24 三. 最大流问题 1. 问题 已知网络D=（V，A，C），其中V为顶点 集，A为弧集，C={cij}为容量集， cij 为弧（vi，vj ） 上的容量。现D上要通过一个流f={f ij}，其中f ij 为弧 （vi，vj ）上的流量。问应如何安排流量f ij可使D上 通过的总流量v最大？ 例如： v2 v4 vs v1 vt v3 2 1 3 1 4 5 3 2 5