第二节网络分析.ppt

2019/4/12,第二节 网络分析,网络赋权图，记D=（V，E，C），其中C=c1，cn， ci为边ei上的权（设ci ）。 网络分析主要内容最小部分树、最短路、最大流。,2019/4/12,一. 最小部分（支撑）树问题,问题：求网络D的部分树，使其权和最小。 方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。,例 3.2 求如图网络的最小部分树。,2019/4/12,避圈法是一种选边的过程，其步骤如下：,1. 从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；,2. 把顶点集V分为互补的两部分V1, 1 ，其中,2019/4/12,用避圈法解例3.2,最小部分树如图上红线所示； 最小权和为14。,思考：破圈法是怎样做的呢？,见圈就破，去掉其中权最大的。,2019/4/12,二. 最短路问题,2. 方法：标号法（Dijkstra，1959） 给每点vj标号dj，vi，其中dj为v1至vj的最短距，vi为最短路上的前一点。,2019/4/12,标号法步骤：,2019/4/12,用标号法解例3.3,0，v1,2，v1,3，v1,其中2=min0+2,0+5,0+3,4，v2,7，v3,8，v5,13，v6,最短距为13；,最短路为v1-v2-v3-v5-v6-v7。,2019/4/12,三. 最大流问题,1. 问题 已知网络D=（V，A，C），其中V为顶点 集，A为弧集，C=cij为容量集， cij 为弧（vi，vj ） 上的容量。现D上要通过一个流f=fij，其中fij 为弧 （vi，vj ）上的流量。问应如何安排流量fij可使D上 通过的总流量v最大？,2019/4/12,2. 数学模型,（容量约束） （平衡条件）,问题：最大流问题的决策变量、目标函数、约束条件各是什么？,2019/4/12,3. 基本概念与定理,如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。,2019/4/12,（2）可增值链（增广链）,2019/4/12,（3） 截集与截量,截量：截集上的容量和，记为 。,例3.4 对于下图，若V1=vs，v1，请指出相应的截集与截量。,2019/4/12,解：,2019/4/12,（4） 流量与截量的关系,截集上的流量和,相应于截 集的反向 弧上流量和,最大流最小割定理：,2019/4/12,4. 解法,（5） 最大流的判别条件,2019/4/12,步骤：,2019/4/12,2019/4/12,例3.5 用标号法求下面网络的最大流。,2,0,2,0,解：第一次标号及所得可增值链如图，调量 =1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量v=5，同时得最小截,