1、第5章 图论与网络分析,图的基本概念,网络分析,最小支撑树问题 最短路径问题网络最大流问题,图论起源：哥尼斯堡七桥问题,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,结论：每个结点关联的边数均为偶数,1 图的基本概念,由点和边组成，记作G=(V，E)，其中V=(v1，v2，vn)为结点的集合，E=(e1，e2，em) 为边的集合。,点表示研究对象,边表示研究对象之间的特定关系,1. 图,p114,图,无向图，记作G=(V，E),有向图，记作D=(V，A),例1：哥尼斯堡桥问题的图为一个无向图。,有向图的边称为弧。,2、图的分类,例,图1,图2,3、链与
2、路、圈与回路,链,点边交错的序列,路,点弧交错的序列,回路,起点=终点的路,无向图：,有向图：,链与路中的点均不相同，则称为初等链 (路)类似可定义初等圈（回路）,4、连通图,G1为不连通图， G2为连通图,例 ：,5、支撑子图,图G=(V，E)和G=(V ，E )，若V =V 且E E ，则称G 为G的支撑子图。,G2为G1的支撑子图,例 ：,G2 是G1 的子图；,例 ：,6、赋权图（网络）,图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。,例 ：,2 最小支撑树问题,本节主要内容：,树,支撑树,最小支撑树,树：无圈的连通图，记为T。,一、树的概念与性质,树的
3、性质： （1）树的任2点间有且仅有1链； （2）在树中任去掉1边，则不连通；故树是使图保持 连通且具有最少边数的一种图形 （3）在树中不相邻2点间添1边，恰成1圈； （4）若树T有m个顶点，则T有m-1条边。,若一个图 G =（V , E）的支撑子图 T=（V , E） 构成树，则称 T 为G的支撑树，又称生成树。,二、图的支撑树,例,例 某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？,解：,该问题实为求图的支撑树问题，共需铺4条路。,图的支撑树的应用举例,用破圈法求出下图的一个生成树。,最小支撑树：求网络的支撑树，使其权和最小
4、。,三、最小支撑树问题,算法1（破圈法）：在给定的赋权的连通图上找一个圈；在所找的圈中去掉一条权数最大的边(若有两条或两条以上的边都是权数最大的边，则任意去掉其中一条)：若所余下的图已不含圈，则计算结束，所余下的图即为最小支撑树，否则，返问。,例 求上例中的最小支撑树,解：,5,5.5,v1,v2,v3,v4,v5,3.5,7.5,4,2,3,4,算法2（避圈法）：从某一点开始，把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数） 。,最小生成树举例：某六个城市之间的道路网如图 所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。
5、,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,联系今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,练习今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤
6、气管道路线，并求所需的总费用。,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,例今
7、有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,此即为最经济的煤气管道路线，所需的总费用为25万元,3最短路径问题,最短路问题是在一个网络（赋权有向图）中寻找从起点到某个节点之间一条最短的路线。现欲求出1至6距离最短的路径。,基本思想：从起点vs开始，逐步给每个结点vj标号dj ,vi，其中dj为起点vs到vj的最短距离， vi为该最短路线上的前一节点. 若给终点vt标上号dt ,vi, 表示已求出v1至vt的最短路其最短路长为 dt ，最短路径可根据标号 v
8、i 反向追踪而得,最短路问题的Dijstra解法 （狄克拉斯）,0, v1,1, v1,(3) 考虑所有这样的边vi , vj，其中viVA， vjVB，挑选其中与起点v1距离最短（mindi+cij）的vj，对vj进行标号,(4) 重复(2)、(3)，直至终点vn标上号dn, vi，则dn即为v1 vn的最短距离，反向追踪可求出最短路。,(1)给起点v1标号0, v1,0, v1,1, v1,(3) 考虑所有这样的边vi , vj，其中viVA， vjVB，挑选其中与起点v1距离最短（mindi+cij）的vj，对vj进行标号,(4) 重复(2)、(3)，直至终点vn标上号dn, vi，则d
9、n即为v1 vn的最短距离，反向追踪可求出最短路。,(1)给起点v1标号0, v1,3, v1,0, v1,1, v1,3, v1,5, v3,0, v1,1, v1,3, v1,5, v3,6, v2,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,12, v5,此时终点v9已标号12, v5，则12即为v1 vn的最短距离，反向追踪可求出最短路,0, v1,1, v1,3, v1,5, v3,6,
10、 v2,9, v5,10, v5,12, v5,v1到v9的最短路为：v1 v3 v2 v5 v9，最短距离为12,p119,练习：用Dijkstra算法求下图中V1至V8的最短路及最短路长。,关键线路：1.V1-V2-V4-V6-V82.V1-V2-V4V7-V8最短路长：12,课堂练习 无向图情形,求网络中v1至v7的最短路。,课堂练习 无向图情形,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/ v4,7,v3,8,v5,13,v6,课堂练习 无向图情形,答案（2）：,v1,v2,v3,v4,v5,v6,v
11、7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/ v4,7,v3,8,v5,13,v6,最短路模型的应用设备更新问题,例 某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,最短路模型的应用设备更新问题,分析：,结点：V=v1，v6， vi表示第i年初；,弧： A=(vi，
12、vj) 表示第i年初购买，用至第j年初；i= 1,5; j= 2,6,权cij： i年初 j年初的费用，即cij= i年初购买费+（j-i）年里的维修费,通路：表示一个更新策略。例如v1-v2-v6表示第一年购买用到第二年更新，继续用至第五年末的一个更新策略,最短路模型的应用设备更新问题,0,v1,16,v1,22,v1,30,v1,41,v1,53,v3/v4,16,30,22,41,59,16,22,30,41,17,23,31,17,23,18,建模：,求解：,求得两个最优更新策略：v1-v4-v6，即第一年购买设备，用到第四年更新，再用至第五年年末V1-v3-v6，即第一年购买设备，用
13、到第三年更新，再用至第五年年末最优费用为53,计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,练习：设备更新问题,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,算法的基本思路与步骤： 首先设任一点vi到任一点vj都有一条弧。无弧相连的点之间假设存在权为+的弧相连。 从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi ,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。 设
14、P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：,(二) Ford法(逐次逼近法) （权有负数）,开始时，令 即用v1到vj的直接距离做初始解。,从第二步起，使用递推公式：,求 ，当进行到第t步，若出现,即为v1到各点的最短路长。,则停止计算，,例:,从第二步起，使用递推公式,从第二步起，使用递推公式,为了求出从v1到各个点的最短路，一般采用反向追踪的方法：如果已知d(vs ,vj),那么寻求一个点vk ,使得d(vs,vk)+wkj=d(vs ,vj) ,然后记录下(vk ,vj)；在看d(vs ,vk) ,寻求一个点vi ,使得d(vs ,vi)+wik=
15、d(vs ,vk)依次类推，一直到达为止。这样，从vs到vj的最短路是（vs ,vi ,vk ,vj）,d(v1 ,v8)=6, 由于d(v1 ,v6)+w68=(-1)+7记录下v6 由于d(v1 ,v3)+w36=d(v1 ,v6) , 记录下v3 由于d(v1 ,v1)+w13=d(v1 ,v3), 于是，从v1到v8的最短路是(v1 ,v3 ,v6 ,v8)。,4 网络最大流问题,引例：下图为V1到V6的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V1到V6的运输产品数量最多。,已知网络D=（V，A，C），其中V为顶点集，A为弧集，C=cij为容量集， cij 为弧（vi
16、，vj ）上的容量。现D上要通过一个流f=fij，其中fij 为弧（vi，vj ）上的流量。问题：应如何安排流量fij可使D上通过的总流量v最大？,一、一般提法,二、最大流问题的数学模型,max v=v（f）,容量约束,平衡约束,P125,满足上述所有约束条件的流成为可行流。,（1）容量条件：对于每一个弧（vi ,vj）A，有0 fij cij 。 （2）平衡条件： 对于发点vs，有 对于收点vt ，有 对于中间点，有 为可行流f 的流量(发点的净输出量或收点的净输入量),1、称满足下列条件的流f为可行流：,三、 基本概念和定理,可行流特征：（1）容量条件：每一个弧上的流量不能超过该弧的容量。
17、（2）每一个中间点的流入量与流出量的代数和为零。（转运的作用）（3）出发点的总流出量与收点的总流入量必相等。,任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。,可行流中 fijcij 的弧叫做饱和弧； fijcij的弧叫做非饱和弧； fij0 的弧叫做非零流弧； fij0 的弧叫做零流弧。,2、饱和弧与零流弧,f为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,3、增广链,增广链,显然图中增广链不止
18、一条,增广链,容量网络D =（V，A，C），vs为始点，vt为终点。如果把V分成两个非空集合 使 则所有始点属于V1，而终点属于 的弧的集合 ，称为分离vs和vt的截集。,4、截集和截集的截量,截集是连接起点和终点的必经之路。,截集 中所有弧的容量之和，称为这个截集的截量，记为,则截集为,设,容量为24,设,则截集为,容量为20,流量与截量的关系：,任一可行流的流量都不会超过任一截集的截量,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,最大流最小截定理：任一网络D中，从v s至v t 的最大流的流量等于分离v s、v t 的最
19、小截集的容量。,例. 如图所示的网络中，弧旁数字为(cij ,fij ),v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）确定所有的截集；（2）求最小截集的容量；（3）证明图中的流为最大流；,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，,截集为(vs,v1), (vs,v2)，截量为：6,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：,
20、 V1=vs，截集为(vs,v1), (vs,v2)，截量为：6,V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集为(vs,v1), (vs,v2)，截量为：6V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7V1=vs ,v2，截集为，截量为：7, V1=vs，截集为(vs,v1), (vs,v2)，截量为：6V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7V1=vs ,v2，
21、截集为，截量为：7V1=vs ,v3，截集为，截量为：12,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集为(vs,v1), (vs,v2)，截量为：6V1=vs ,v1，截集为(vs,v2), (v1,vt)，截量为：7V1=vs ,v2，截集为，截量为：7V1=vs ,v3，截集为，截量为：12V1=vs ,v1,v2，截集为，截量为：5,（2）最小截量
22、min C (V1,V2)= 5；（3）v(f*)=5= min C (V1,V2) f*是最大流。,最大流判定定理： 可行流f* 是最大流的充分必要条件是当且仅当不存在从vs到vt 的关于f *的增广链。,p124,寻求网络最大流问题的主要步骤：（1）确定初始可行流（观察法和零流法）（2）检验当前可行流是否是网络中的最大流(对已知可行流用标号法寻找可扩充链，若存在，则当前可行流不是最大流，转(3)；若不存在，则是最大流）（3）将当前的可行流调整成一个流量更大的新可行流再由(2)检验,四、求最大流方法标号法,思路：从始点开始标号，寻找是否存在增广链。给vj标号为j,vi，其中j为调整量， vi
23、为前一节点。,标号具体步骤：,（b） 标号终止，说明不存在可扩充链，当前即为流为最大流，并得最小截集,（a） 说明存在可扩充链,反向追踪找出 ,转(4),例5 用标号法求下面网络的最大流。,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,步骤：(1)给vs标号为,vs， 选与vs关联的流出未饱和弧(vs, vj) ,给vj标号j,vs,其中j=csj-fsj,例5 用标号法求下面网络的最大流。,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,例5 用标号法求下面网络的最大流。
24、,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,例5 用标号法求下面网络的最大流。,vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。,（4）重复（2）,（3），依次进行的结局可能为：,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,例5 用标号法求下面网络的最大流。,vt已标号，得到一条增广链u(反向
25、追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。,（4）重复（2）,（3），依次进行的结局可能为：,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,例5 用标号法求下面网络的最大流。,vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。,（4）重复（2）,（3），依次进行的结局可能为：,例5 用标号法求下面网络的最大流。,(5)调整。取 =t，令,，得新流 fij转(1)。,（2,2）,（1,0）,（3,3）,（1,1）,（4,4）,（5
26、,2）,（3,0）,（2,1）,（5,4）,此时标号无法进行，当前流为最大流，最大流量为5；最小截为(vs,v2), (v1,v3)，截量为：5,练习： 有三个发电站v1,v2,v3，发电能力分别为15、10和40兆瓦，经输电网可把电力送到8号地区，电网能力如图所示。求三个发电站输到该地区的最大电力。,v0,（1）由于网络图中只有一个发点和一个收点，所以有必要添加一个虚设的起点 和弧 弧上各容量为 ，分别为三点 的发电能力，如图所示：,v0,10,10,15,15,15,0,10,10,10,10,15,25,(2)由观察法得一初始可行流 即图上所标 。 为弧 上容量， 为弧上流量。,(2)由
27、观察法得一初始可行流 即图上所标 。 为弧 上容量， 为弧上流量。,v3,(40,10),(15,15),(30,10),(15,15),(45,25),(10,10),(15,15),(10,0),(20,10),v0,(10,10),(15,15),(40,10),(3)用标号法寻找可扩充链,v0,|,|,v6,|,v5,v4,|,v2,v1,v7,v8,反向追踪，得一v0-v8的可扩充链:v0-v3-v6-v5-v2-v7-v8,v3,(40,10),(15,15),(30,10),(15,15),(45,25),(10,10),(15,15),(10,0),(20,10),v0,(10
28、,10),(15,15),(40,10),v0,|,|,v6,|,v5,v4,|,v2,v1,v7,v8,(4)调整流量。由可扩充链确定一新可行流 ，可扩充链上前向弧上流量均增加,(45,35),(40,20),(10,10),(20,20),(30,20),(40,20),(5)继续用标号法检验当前可行流是否为最大流,v3,(40,20),(15,15),(30,20),(15,15),(45,35),(10,10),(15,15),(10,10),(20,20),v0,(10,10),(15,15),(40,20),v0,|,|,v6,|,v5,v4,v2,v1,v7,v8,|,标号完毕，
29、且终点未标号。这说明网络中已找不到可扩充链，当前即为最大流，最大流流量为： 20+15+1045即三个发电站输送到8号地区的最大电力为45兆瓦。,练习：图中A、B、C、D、E、F分别表示陆地和岛屿，表示桥梁及其编号。河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。,分析：转化为一个网络图，弧的容量为两点间的桥梁数。,则问题为求最小截。,步骤（1）确定初始可行流,1(1),1(0),分析：转化为一个网络图，弧的容量为两点间的桥梁数。,则问题为求最小截。,答案：最小截为AE、CD、CF,A,B,C,D,E,F,2(1),1
30、(1),1(1),1(1),1(0),2(2),2(1),2(1),2(1),2(2),2(2),步骤（1）确定初始可行流,（2）标号法求最大流得最小截,1(0),1(0),2(0),2(0),2(0),案例：有一批人从我国A城赴俄罗斯B城，可能的旅行路线如图：,边防队拟建立足够数量检查站以便使每辆汽车至少必经过一个检查站，建立检查站的费用根据各路段条件有所不同（如图数字所示），求最小费用解。,（分析：最小截问题）,分析：转化为一个网络图，弧的容量为各路段得费用。则问题为求最小截。 步骤,a,B,A,b,c,d,e,f,g,4,6,8,2,3,2,5,7,3,8,4,3,7,6,4,4(4),
31、6(6),8(3),2(2),3(3),2(2),5(5),7(6),3(0),8(4),4(3),3(3),7(3),6(6),4(4),（1）确定初始可行流,（2）标号法求最大流得最小截,答案：最小截为Aa、Ab、cb，即在这三个路段修建检查站，最小费用为13,案例：垃圾处理问题 某地区有3个城镇，各城镇每天产生的垃圾要运往该地区的4个垃圾处理场处理，现考虑各城镇到各处理场的道路对各城镇垃圾外运的影响。假设各城镇每日产生的垃圾量、各处理场的日处理能力及各条道路（可供运垃圾部分）的容量（其中容量为0表示无此直接道路）如右表所示，试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理场得到处
32、理，如果不能，应首先拓宽哪条道路。,分析：转化为一个网络图，弧的容量为各路段能处理垃圾的数量。,a,b,c,1,2,3,4,s,t,80,50,40,20,50,60,40,90,30,20,70,30,50,10,20,40,则问题为求最小截。,b,80(80),50(30),40(20),20(0),50(30),60(60),40(40),90(20),30(30),20(20),70(20),30(30),50(50),10(0),20(20),40(0),80,50,40,20,50,60,40,90,20,70,30,50,10,20,40,s,（1）确定初始可行流,30,（2）标
33、号法求最大流得最小截,4,c,3,2,1,a,t,b,80(80),50(30),40(20),20(0),50(30),60(60),40(40),90(20),30(30),20(20),70(20),30(30),50(50),10(0),20(20),40(0),s,（3）反向追踪，找可扩充链,4,c,3,2,1,a,t,90(40),20(20),50(10),40(20),70(40),得一s-t的可扩充链:,s-b-4-c-3-t，调整量,b,90(40),50(10),40(20),70(40),80(80),50(30),40(20),20(20),60(60),40(40)
34、,30(30),20(20),30(30),50(50),10(0),20(20),（4）重复标号,3,2,1,a,t,s,4,c,a,2,1,a,3,（5）反向追踪，找可扩充链,（6）找到可扩充流S-b-4-c-3-t,调整量为10,b,80(80),50(40),40(20),20(20),60(60),40(40),30(30),20(20),30(20),50(50),10(10),20(20),3,2,1,a,t,s,4,c,a,2,1,a,3,（6）找到可扩充流S-b-4-c-3-t,调整量为10,90(50),50(0),40(30),70(50),90(50),20(20),5
35、0(0),40(30),70(50),80(80),50(40),40(20),60(60),40(40),30(30),20(20),30(20),50(50),10(10),20(20),（4）重复标号，直至终止,3,2,1,a,t,c,3,2,1,a,t,s,b,4,答案：最小截为sa、sc、b3 、4t ,垃圾最大处理量为180 50+70+80,答案,综上，目前的道路状况不能使所有垃圾都运到处理场得到处理。 从图上不难发现，理论上应当拓宽割集所在的道路。但由于sa,sc和4t都是添加的虚拟道路，所以只有拓宽割集中的b3道路的路宽，或者增大4号处理场处理垃圾的能力，才能解决问题。,练习
36、：过纽约ALBANY的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/小时。求（1）该路网能承受的北-南向最大流量；（2）若要扩充通过能力，应在那一组路段上扩充，说明原因。,(1)选取一个可行流,1,2,3,5,4,6,（,进入Albany(北),离开Albany(南),2(2),4(1),3(0),1(1),6(5),3(3),2(2),3(3),6(2),1(1),V1V4V2V5V6，可扩充量为1，调整成新流，继续标号,用标号法得可扩充链,1,2,3,5,4,6,（,进入Albany(北),离开Albany(南),2(2),4(2),3(1),1(1),6(5),3(3)
37、,2(2),3(3),6(3),1(0),标号终止，当前流为最大流，最大流量为8割集为：12, 45， 46，36应该在割集弧上扩大流量,练习1,0, v1,4, v1,3, v1,5, v2,6, v2,9, v7,7, v4/ v6,8.5, v6,6, v2,有9个城市v1、 v2、v9，其公路网如图所示。弧旁数字是该段公路的长度，有一批物资要从v1 运到v9 ，问走哪条路最近？,习题课练习（最小支撑树）,已知有A、B、C、D、E、F六个城镇间的道路网络 如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。,练习
38、2,第四节 最小费用最大流问题,在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。,设一个网络D=（V，A，C），对于每一个弧(vi ,vj )A ,给定一个单位流量的费用bij 0 ，网络系统的最小费用最大流问题，是指要寻求一个最大流 f ，并且流的总费用 达到最小。,而此时总费用b(f )比b(f)增加了,我们将 叫做这条增广链的费用。,我们首先考察，在一个网络D中，当沿可行流 f 的一条增广链，以调整量=1改进f ，得到的
39、新可行流f 的流量，有 v(f )= v(f )+1,显然，零流f =0是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f =0开始。 问题是：如果已知f 是流量为v(f)的最小费用流，如何寻找关于f 的最小费用增广链？,结论：若f 是流量为v(f )的所有可行流中的费用最小，而 是关于f 的所有增广链中的费用最小的增广链，则 f 沿增广链调整量为1得到的新可行流f ，一定是流量为v(f )+1的所有可行流中的最小费用流。 依次类推，当 f 是最大流时，就是所要求的最小费用最大流。,若u是从vs到vt关于f的增广链，它的费用,若果把u- 中的边(v i ,vj)反向，并且令它的权是
40、-bij，而u+中的方向不变，并且的它的权是bij，这样就把求从vs到vt关于f 的最小费用增广链就转换成寻求从vs 到vt 的最短路。,构造一个赋权有向图 M( f )，其顶点是原网络D的顶点，他的边根据f 的情况确定：,若原图中（vi ，vj）边中fij=0，则M( f )中连接（vi，vj）,并令其权L(vi ,vj)=bij；若原图中（vi，vj）边中fij =cij，则M( f )中连接（vi，vj）,并令其权L(vi ,vj)=-bij；若原图中（vi，vj）边中fij=0，则M( f )中连接（vi，vj）和(vj ,vi),并令其权L(vi ,vj )=bij , L(vi ,
41、vj )=-bij ；,步骤： （1）取零流为初始可行流 ，f (0) =0。（2）一般地，如果在第k-1步得到最小费用流 f (k-1)，则构造图 L( f (k-1) )。（3）在L( f (k-1) )中，寻求从vs到vt的最短路。若不存在最短路，则f (k-1)就是最小费用最大流；否则转(4)。（4）如果存在最短路，则在可行流f (k1)的图中得到与此最短路相对应的增广链，在增广链上，对f (k1)进行调整，调整量为：,得到新可行流f (k) 。对f (k)重复上面步骤，返回（2）。,例 求图8-24 所示网络中的最小费用最大流，弧旁的权是（bij , cij）.,图 8-24,4,由于在M( f (4)中已经不存在从vs到vt的最短路，因此，可行流f (4)，v(f(4)=11是最小费用最大流。,例8.11 求网络的最小费用最大流，弧旁权是（bij , cij）,
