图与网络分析

图与网络分析第一页，共一百六十页，编辑于2023年，星期二近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。第一节图的基本概念与模型Königsberg桥对应的图第二页，共一百六十页，编辑于2023年，星期二例1、有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况也可以用图表示出来。V1V2V3V4V5e5e4e1e2e3e6e7一、图基本概念第三页，共一百六十页，编辑于2023年，星期二例2某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映这个情况可以用点V1,V2,……V8分别代表这八种药品，若药品Vi和药品Vj是不能存放在同一个库房的，则在Vi和Vj之间连一条线。•V1V2

••V3•V4•V5

•·V8•V7•V6第四页，共一百六十页，编辑于2023年，星期二图的表示方法：

一般地，当用图论研究一个实际问题时，常以顶点（Vertex）表示要研究的对象，以它们之间的连线，表示某种关系，这种连线称为边（Edge），目的是为了解决某个极值问题。图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1];e2=[v1,v2];第五页，共一百六十页，编辑于2023年，星期二运筹学中研究的图具有下列特征:

强调点与点之间的关联关系，不讲究图的比例大小与形状；每条边上赋有一个权；建立网络模型，求最大值或最小值。第六页，共一百六十页，编辑于2023年，星期二下图可以提出很多极值问题142653876631627433716第七页，共一百六十页，编辑于2023年，星期二v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。二、关于图的另外一些名称和术语：第八页，共一百六十页，编辑于2023年，星期二环,多重边,简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5第九页，共一百六十页，编辑于2023年，星期二次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。第十页，共一百六十页，编辑于2023年，星期二定理1任何图中，顶点次数之和等于所有边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：2m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。第十一页，共一百六十页，编辑于2023年，星期二链，圈，连通图图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。第十二页，共一百六十页，编辑于2023年，星期二子图，部分图(支撑子图)图G1={V1、E1}和图G2={V2，E2}如果有称G1是G2的一个子图。若有，则称G1是G2的一个部分图(支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）第十三页，共一百六十页，编辑于2023年，星期二网络（赋权图）赋权图）:权可以代表距离、费用、通过能力(容量)等等。无向网络:端点无序的赋权图称为.有向网络:端点有序的赋权图称为。①②③④⑤⑥910201571419256第十四页，共一百六十页，编辑于2023年，星期二图的矩阵描述：邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵 对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中第十五页，共一百六十页，编辑于2023年，星期二图的基本概念与模型v5v1v2v3v4v64332256437例6.2下图所表示的图可以构造邻接矩阵A如下第十六页，共一百六十页，编辑于2023年，星期二对于赋权图G=(V,E),其中边有权,构造矩阵B=(bij)nn

其中：2.权矩阵第十七页，共一百六十页，编辑于2023年，星期二v5v1v2v3v4v64332256437例6.4下图所表示的图可以构造权矩阵B如下:第十八页，共一百六十页，编辑于2023年，星期二G=(V,E)矩阵表示A

邻接矩阵B

关联矩阵边e=[u,v]

关联边

端点

重合环多重边

平行边简单图不含多重图含点的次

01奇数偶数子图子图生成子图孤立点悬挂点奇点偶点顶点数p边数q点边关系各种链的概念第十九页，共一百六十页，编辑于2023年，星期二欧拉图与中国邮路问题欧拉图哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？第二十页，共一百六十页，编辑于2023年，星期二Cab图4-10ad哥尼斯堡七桥问题第二十一页，共一百六十页，编辑于2023年，星期二acbd(b)第二十二页，共一百六十页，编辑于2023年，星期二定理2连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点。定义1.在连通无向图G中,若存在经过每条边恰好一次的一个圈或一条链,就称此圈或链为欧拉圈或欧拉链。若图G含一条欧拉圈，则称为欧拉图。定理1连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点。（G中无奇次顶点）第二十三页，共一百六十页，编辑于2023年，星期二欧拉链欧拉图第二十四页，共一百六十页，编辑于2023年，星期二中国邮路问题第二十五页，共一百六十页，编辑于2023年，星期二定理3使图G成为总权最小的欧拉图的充要条件是：（1）在有奇次顶点的图G中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重复边。（2）在图G的每个回路上，重复边之总权不超过该回路非重复边之总权。（或回路总长的一半）

第二十六页，共一百六十页，编辑于2023年，星期二例1试为图4-13（a)构成总权最小的欧拉图。图中线旁的数字为相应边的权。124332124（a)图4-13第二十七页，共一百六十页，编辑于2023年，星期二例2试为图4-14（a）所示的街道规划最优投递路线。解：可按以上所述步骤进行，最终结果示于图4-14（b)，总权等于52，重复边的长度等于10。1334333333222图4-14（a）2第二十八页，共一百六十页，编辑于2023年，星期二413333333322图4-14（b）22第二十九页，共一百六十页，编辑于2023年，星期二第二节树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例6.2乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员第三十页，共一百六十页，编辑于2023年，星期二例6.3某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科第三十一页，共一百六十页，编辑于2023年，星期二树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6第三十二页，共一百六十页，编辑于2023年，星期二图的最小部分树(支撑树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2第三十三页，共一百六十页，编辑于2023年，星期二

例如，图4-18（a）是一个有四个顶点（n=4）的连通图，它共有nn-2=42=16个生成树。V1V2V3V4图4-18（a）第三十四页，共一百六十页，编辑于2023年，星期二第三十五页，共一百六十页，编辑于2023年，星期二第三十六页，共一百六十页，编辑于2023年，星期二abcfedhgbfed第三十七页，共一百六十页，编辑于2023年，星期二abcfedhgbfdg第三十八页，共一百六十页，编辑于2023年，星期二bcedabcfedhg第三十九页，共一百六十页，编辑于2023年，星期二abchabcfedhg第四十页，共一百六十页，编辑于2023年，星期二afdgabcfedhg第四十一页，共一百六十页，编辑于2023年，星期二赋权图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=5第四十二页，共一百六十页，编辑于2023年，星期二v1v2v3v4v5v643521得到最小树：MinC(T)=15第四十三页，共一百六十页，编辑于2023年，星期二避圈法:

去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618第四十四页，共一百六十页，编辑于2023年，星期二v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15第四十五页，共一百六十页，编辑于2023年，星期二v1v7v4v3v2v5v620159162532817412336练习：应用破圈法求最小树第四十六页，共一百六十页，编辑于2023年，星期二v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57第四十七页，共一百六十页，编辑于2023年，星期二课堂练习：3749346321MinC(T)=12MinC(T)=15254173314475答案：第四十八页，共一百六十页，编辑于2023年，星期二34122323242MinC(T)=12213638534567454321MinC(T)=18第四十九页，共一百六十页，编辑于2023年，星期二

某一点到另一点的最短路的Dijkstra法所有点对间的最短路

返回第三节最短路问题第五十页，共一百六十页，编辑于2023年，星期二 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.

有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。第五十一页，共一百六十页，编辑于2023年，星期二里特城（Littletown）是一个乡村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供服务。在这个地区里有很多道路，从消防站到任何一个社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素，所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。例子：里特城的消防队问题第五十二页，共一百六十页，编辑于2023年，星期二第五十三页，共一百六十页，编辑于2023年，星期二最短路：O—A—B—E—F—T19英里第五十四页，共一百六十页，编辑于2023年，星期二一、求最短路的Dijkstra算法

1、算法的基本思想第五十五页，共一百六十页，编辑于2023年，星期二2.有向图的狄克斯屈拉(Dijkstra)标号算法步骤点标号：p(vj)—起点vs到点vj的最短路长；边标号：a(i，j)=p(i)+lij，步骤：(1)令起点的标号；p(vs)

＝0。先求有向图的最短路，设网络图的起点是vs,终点是vt,以vi为起点vj为终点的弧记为（i，j）,距离为lij(2)找出所有vi已标号vj未标号的弧集合Ai={(i，j)}，如果这样的弧不存在或vt已标号则计算结束；(3)计算集合Ai中弧的标号：a(i，j)=p(i)+lij(4)选一个点标号返回到第(2)步。第五十六页，共一百六十页，编辑于2023年，星期二①②③④⑤⑥⑦610123214675811165图5－19【例5-1】图5－1中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。第五十七页，共一百六十页，编辑于2023年，星期二【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij＝1，不选择弧(i，j)时xij＝0，得到最短路问题的网络模型：第五十八页，共一百六十页，编辑于2023年，星期二②③④⑤⑥⑦610123214675811165图5－1961012920p(9,v2)18P（6,V1）①16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)【例5-1】用Dijkstra算法求图5－1所示v1到v7的最短路及最短路长v1到v7的最短路为：p17=｛v1,v2,v3,v5,v7｝，最短路长为L17=2914P（0,V1）第五十九页，共一百六十页，编辑于2023年，星期二②③④⑤⑥⑦610123214675811165图5－1961012920p(9,v2)18P（6,V1）①16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)v1到v7的最短路为：p17=｛v1,v2,v3,v5,v7｝，最短路长为L17=2914P（0,V1）第六十页，共一百六十页，编辑于2023年，星期二从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。第六十一页，共一百六十页，编辑于2023年，星期二【例6-5】求图6-10所示v1到各点的最短路及最短距离①②③④⑤⑥⑦⑧452617839326121618P(0,v1)452P(2,v1)310P(3,v1)96126P(4,v1)11P(6,v3)P(6,v3)1881224P(8,v5)24P(18,v5)所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。图6-103.无向图最短路的求法第六十二页，共一百六十页，编辑于2023年，星期二Dijkstra最短路算法的特点和适应范围每次迭代只有一个节点获得标号，若有两个或两个以上节点的临时标号同时最小，可任选一个标号；标号Pj表示vs

到vj

的最短路，第k次迭代得到的永久标号，最多有n1

次迭代；可以应用于简单有向图和混合图，在临时标号时，所谓相邻必须是箭头指向的节点；若第n1

次迭代后仍有节点的标号为，则表明vs

到该节点无有向路径；vs到所有点的最短路也是一棵生成树，但不是最小生成树这个算法只设用于全部权为非负情况,如果某边上权为负的,算法失效;当vi与vj两点之间至少有两条边相关联时，留下一条最短边，去掉其它关联边。第六十三页，共一百六十页，编辑于2023年，星期二1024149135787v1v2v3v4v5v6例求下图所示网络之顶点1至6的最短路和最短路长。P（0，v1）P（10，v1）P（15，v2）P（22，v5）P（22，v5）P（23，v2）第六十四页，共一百六十页，编辑于2023年，星期二142653876631627433716第六十五页，共一百六十页，编辑于2023年，星期二二、所有点对间的最短路Floyd算法1、写出图的权矩阵

第六十六页，共一百六十页，编辑于2023年，星期二步骤：１、输入权矩阵Ｄ（０）＝Ｄ；２、对n个顶点的图G,该方法迭代n步结束，第k次迭代的矩阵Dk的元素dij(k)按下式选取

dij(k)=min{dij(k-1),[dik(k-1）+dkj(k-1）]}其中，i,j=1,2,3,………,n。但当i=k或j=k时，dij(k)=dij(k-1).。３、Ｄ（ｎ）中的元素就是ｖｉ到ｖｊ的最短路长。第六十七页，共一百六十页，编辑于2023年，星期二v1v3v4v2v5512310655228442例求下图所示网络图各点对间的最短路和最短路长。第六十八页，共一百六十页，编辑于2023年，星期二第六十九页，共一百六十页，编辑于2023年，星期二第七十页，共一百六十页，编辑于2023年，星期二第七十一页，共一百六十页，编辑于2023年，星期二第七十二页，共一百六十页，编辑于2023年，星期二23147432910例求下图所示网络图各点对间的最短路和最短路长。第七十三页，共一百六十页，编辑于2023年，星期二课堂练习：1.用Dijkstra算法求下图从v1到v6的最短距离及路线。v3v54v1v2v4v635222421v1到v6的最短路为：第七十四页，共一百六十页，编辑于2023年，星期二2.求从v1到v8的最短路径237184566134105275934682第七十五页，共一百六十页，编辑于2023年，星期二237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路径为v1→v4→v7→v5→v8，最短距离为10第七十六页，共一百六十页，编辑于2023年，星期二最短路问题的应用：例6.7电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。v1（甲地）1517624431065v2v7(乙地)v3v4v5v6第七十七页，共一百六十页，编辑于2023年，星期二解：这是一个求无向图的最短路的问题。第七十八页，共一百六十页，编辑于2023年，星期二第四节网络最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。第七十九页，共一百六十页，编辑于2023年，星期二实例：ＢＭＺ公司的最大流问题

ＢＭＺ公司是欧洲一家生产豪华汽车的制造商。虽然它生产的汽车在所有发达国家的销量都不错，但是对于这家公司来说，出口到美国显得尤其重要。ＢＭＺ公司因为提供优质的服务而获得很好的声誉，保持这个声誉一个很重要的秘诀是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商和授权维修店。这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔需要优先考虑的是改进这些配送中心的不足之处。

背景第八十页，共一百六十页，编辑于2023年，星期二

该公司在美国有几个配送中心。但是，离洛杉矾中心最近的一个配送中心却坐落在离洛杉矾1000多英里的西雅图。由于ＢＭＺ的汽车在加利福尼亚越来越受欢迎，所以保证洛杉矾中心良好的供应就显得尤为重要了。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问题——正如现在卡尔深切领会到了一样。大部分的汽车配件以及新车是在该公司坐落于德国斯图加特的总厂和新车一起生产的。也就是这家工厂向洛杉矾中心供应汽车配件。由于其中的一些配件体积很大，某些配件的需求量很多，这就使得供应的总量非常庞大——每月有超过300，000立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。第八十一页，共一百六十页，编辑于2023年，星期二

卡尔需要尽快做出一个方案，使得下个月从总厂运送到洛杉矾配送中心的供应件尽可能的多。他已经认识到了这是个最大流问题——一个使得从总厂运送到洛杉矾配送中心的配件流最大的问题。因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是该公司配送网络的容量。

问题第八十二页，共一百六十页，编辑于2023年，星期二第八十三页，共一百六十页，编辑于2023年，星期二LASTLIROBONONY806070405030507040BMZ的网络模型，图中的数字代表该弧的容量第八十四页，共一百六十页，编辑于2023年，星期二

一基本概念二求最大流的标号法返回第八十五页，共一百六十页，编辑于2023年，星期二如图4-23是联接某产品产地v1和销售地v6点

的交通网。s①②③④t4844122679第八十六页，共一百六十页，编辑于2023年，星期二s①②③④t4，38,44,04,21,12,22,26,07,49,3第八十七页，共一百六十页，编辑于2023年，星期二一、基本概念：1.容量网络：对网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。s①②③④t4844122679第八十八页，共一百六十页，编辑于2023年，星期二2.网络的最大流

是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流是指加在网络各条弧上的实际流量，记为fij。若fij=0，称为零流。第八十九页，共一百六十页，编辑于2023年，星期二在网络中满足下述条件的流为可行流：（1）、容量限制条件：0fijcij

（2）、平衡条件：第九十页，共一百六十页，编辑于2023年，星期二结论：任何网络上一定存在可行流。（零流即是可行流）网络最大流问题： 指满足容量限制条件和中间点平衡的条件下，使F值达到最大。第九十一页，共一百六十页，编辑于2023年，星期二割与割集割是指容量网络中的发点和收点分割开，并使s→t的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用表示。如下图中，AA′将网络上的点分割成两个集合。并有，称弧的集合={(vs,v3),(v2,v4),(v2,v5)}是一个割。第九十二页，共一百六十页，编辑于2023年，星期二（S，）={(vs,v3),(v2,v4),(v2,v5)}割容量是：9+6+5=20第九十三页，共一百六十页，编辑于2023年，星期二vsv2v3v4v5v6vt（4，0）（13，11）（5，5）（9，9）（5，4）（5，5）（6，6）（5，2）（9，7）（4，4）（4，4）（10，9）第九十四页，共一百六十页，编辑于2023年，星期二定理1在网络中s→t的最大流量等于它的最小割集的容量，即：v＊(f)=c＊(V,V´)第九十五页，共一百六十页，编辑于2023年，星期二流量可增链 在网络的发点和收点之间能找到一条链，在该链上所有指向为s→t的弧，称为前向弧，记作μ+,存在f<c；所有指向为t→s的弧，称为后向弧，记做μ－，若f>0，则称这样的链为增广链。例如下图中，s→v2→v1→v3→v4→t。定理3网络N中的流F是最大流当且仅当N中不包含任何增广链第九十六页，共一百六十页，编辑于2023年，星期二二、求网络最大流的标号法[基本思想]

由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。[基本方法]找出第一个可行流，（例如所有弧的流量fij=0。）用标号的方法找一条增广链首先给发点s标号(∞),标号中的数字表示允许的最大调整量。选择一个点vi

已标号并且另一端未标号的弧沿着某条链向收点检查：第九十七页，共一百六十页，编辑于2023年，星期二如果弧的起点为vi，并且有fij<Cij，则给vj标号为(Cij－fij)如果弧的方向指向vi，并且有fji>0，则vj标号(fji)(3)重复第(2)步，可能出现两种结局：标号过程中断，t无法标号，说明网络中不存在流量可增链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V′,(V,V′)为网络的最小割。t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的流量可增链。继续第(4)步第九十八页，共一百六十页，编辑于2023年，星期二(4)修改流量。设原图可行流为f，令得到网络上一个新的可行流F。(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何流量可增链，计算结束。第九十九页，共一百六十页，编辑于2023年，星期二例6.10用标号算法求下图中s→t的最大流量，并找出最小割。●stv1v3v2v48,79,35,410,86,12,09,95,47,5第一百页，共一百六十页，编辑于2023年，星期二解：(1)先给s标号(∞)●stv1v3v2v48,79,35,410,86,12,09,95,47,5(0,∞)F0=12第一百零一页，共一百六十页，编辑于2023年，星期二●stv1v3v2v48,79,35,410,86,12,09,95,47,5(0∞)(2)检查与s点相邻的未标号的点，因fs1<cs1，故对v1标号=min{∞,cs1-fs1}=1,(s,1)第一百零二页，共一百六十页，编辑于2023年，星期二●stv1v3v2v48,79,35,410,86,12,0,9,95,47,6(0,∞)(s,1)(2)检查与v1点相邻的未标号的点，因f13<c13，故对v3标号=min{1,c13-f13}=min{1,6}=1(v1,1)第一百零三页，共一百六十页，编辑于2023年，星期二●stv1v3v2v48,79,35,410,86,12,09,95,47,5(0,∞)(s,1)(v1,1)(3)检查与v3点相邻的未标号的点，因f3t<c3t，故对vt标号=min{1,c3t-f3t}=min{1,1}=1(v3,1)找到一条增广链s→v1→v3→t第一百零四页，共一百六十页，编辑于2023年，星期二第一百零五页，共一百六十页，编辑于2023年，星期二●stv1v3v2v48,89,45,510,86,12,09,95,47,5F1=12+1=13(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。第一百零六页，共一百六十页，编辑于2023年，星期二(5)重复上述标号过程，寻找另外的增广链。●stv1v3v2v48,89,45,510,86,12,09,95,47,5(0，∞)(s,2)(-v2,2)(v1,2)(-v3,1)(v4,1)第一百零七页，共一百六十页，编辑于2023年，星期二(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。●stv1v3v2v48,89,55,510,96,02,09,95,37,6(0，∞)F2=13+1=14第一百零八页，共一百六十页，编辑于2023年，星期二●stv1v3v2v48,89,55,510,96,02,09,95,37,6(0，∞)(s,1)(-v2,1)(v1,1)Fmax=14(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。第一百零九页，共一百六十页，编辑于2023年，星期二例6.9求下图s→t的最大流，并找出最小割stv1v2v3v4v54,33,210,43,21,14,33,25,34,22,27,68,3●F0=9第一百一十页，共一百六十页，编辑于2023年，星期二解:初始可行流：14存在增广链:s→v2→v3→t流量可增值=2F1=9+2=11(2)s→v2→v5→v3→t流量可增值=1F1=11+1=12(3)s→v5→v3→t流量可增值=1F1=12+1=13(4)s→v1→v5→v4→t流量可增值=1F1=13+1=14第一百一十一页，共一百六十页，编辑于2023年，星期二stv1v2v3v4v54,43,310,73,31,14,43,35,54,42,27,78,7●(0,∞)(s,3)无法标号，不存在增广链，此可行流已为最大流。最大流量为14。第一百一十二页，共一百六十页，编辑于2023年，星期二

第五节最小费用流

无限配送公司有两个工厂生产产品，这些产品需要运到两个仓库里。下面是一些具体的信息。

工厂1生产80个单位。工厂2生产70个单位。仓库1需要60个单位。仓库2需要90个单位。（每个单位对应货车满载时的产品数量。）

例子：无限配送公司的问题第一百一十三页，共一百六十页，编辑于2023年，星期二下图给出了运输这些产品可利用的配送网络。在图中，FI和FZ代表两个工厂，W1和W2代表两个仓库，DC表示一个配送中心。箭头表示可行的运输线路。特别地，工厂1和仓库1之间以及工厂2和仓库2之间各有一条铁路运输轨道。（在铁路上的运输量是没有限制的。）除此以外，卡车司机总共可以从工厂运输50个单位到配送中心，然后可以从配送中心运输50个单位到仓库。（任何运输到配送中心的产品必须随后运送到仓库里。）第一百一十四页，共一百六十页，编辑于2023年，星期二第一百一十五页，共一百六十页，编辑于2023年，星期二每条路线的单位运输成本如图6．2中箭头上方的数字所示第一百一十六页，共一百六十页，编辑于2023年，星期二

不同运输路线的运输成本是不一样的。每条路线的单位运输成本如图6．2中箭头上方的数字所示。

管理者的目标是确定一个运输方案（即每条路线运送多少单位的产品），使运输成本的总和达到最小。第一百一十七页，共一百六十页，编辑于2023年，星期二w2w1F1答案如下图所示，每条路线中的运输数量都已经在圆括号里标出。成本，此解决方案的总运输成本是：（80）（70）＄700（-60）（-90）＄300＄200（50,50）＄400＄400＄900（50.,30）（50,50）（50，30）（∞，30）（∞，40）F1F2第一百一十八页，共一百六十页，编辑于2023年，星期二总运输成本=３０（＄７００）＋５０（＄３００）＋５０（＄４００）＋５０（＄２００）＋５０（＄４00）＋２０（＄９００）＝＄１０４，０００第一百一十九页，共一百六十页，编辑于2023年，星期二二、最小费用最大流该方法的迭代步骤如下。１.任给一最小费用可行流。由于bij≥0，故fij=0（vi,vj∈V,(vi,vj)∈A）必是一个最小费用可行流，因而常从零流开始迭代。２.给网络的弧aij赋权；当作为正向弧使用时：第一百二十页，共一百六十页，编辑于2023年，星期二bij+

=bij，若cij-fij>0∞，若cij-fij=0当作为反向弧使用时：bij-=-bij，若fij>0∞，若fij=0为了便于计算和检查，常在每条弧上依次注出以下四个数字：(1)弧容量cij；(2)弧流量fij；(3)bij+

（作为正向弧使用时在其上流过单位物品的费用）；(4)bij-（作为反向弧使用时在其上流过单位物品的费用）。３.以bij+或bij-弧aij的权（弧长），用Dijkstra算法求vs→Vi的最短路P。

4.取增流量△min=min{△ij}aij∈P第一百二十一页，共一百六十页，编辑于2023年，星期二对P上的各弧增流，这里的△ij为弧△ij的流量可增值。5.转回第2步，直至每3步求不出有限长的最短路为止。这时已得到最小费用的最大流。例12求下图网络的最小费用最大流，各弧的容量（弧旁的第一个数字和通过单位物品的费用（弧旁的第二个数字）如图中所示。１s２３t4,16,65,22,33,26,46,3返回第一百二十二页，共一百六十页，编辑于2023年，星期二

讨论1、标号过程中，是否一定要对所有的顶点全部逐个顺序标记？2、如果可以同时得到若干条增广链是否可以同时调整流量？第一百二十三页，共一百六十页，编辑于2023年，星期二3、同一个问题每一次标号过程所寻找的增广链是否唯一？最大流是否唯一？最小割是否唯一？4、对多发点、多收点的容量网络怎麽求最大流？第一百二十四页，共一百六十页，编辑于2023年，星期二比赛安排问题有5名运动员参加游泳比赛，下表给出了每位运动员参加的项目。问如何安排，才能使得每位运动员都不连续地参加比赛？第七节应用举例第一百二十五页，共一百六十页，编辑于2023年，星期二游泳比赛运动员及参加项目运动员50m仰泳50m蛙泳100m蝶泳100m自由泳200m自由泳A

*

B**＊Ｃ＊＊Ｄ＊＊Ｅ＊

*

第一百二十六页，共一百六十页，编辑于2023年，星期二●●●●●v1v5v4v3v2图1游泳比赛安排{v4,v1,v2,v3,v5}第一百二十七页，共一百六十页，编辑于2023年，星期二线路铺设问题下图是一个城镇的地图，现在要在该城镇的各地点间铺设管道已知各点相互之间的铺设费用（单位：千元），如何设计铺设线路，使各地互通的总铺设费用最少？3871245257410679851其最小总费用为：31（千元）第一百二十八页，共一百六十页，编辑于2023年，星期二例6.8设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表年份12345年初价格1111121213第一百二十九页，共一百六十页，编辑于2023年，星期二设备维修费如下表使用年数0-11-22-33-44-5每年维修费用5681118解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6第一百三十页，共一百六十页，编辑于2023年，星期二把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723第一百三十一页，共一百六十页，编辑于2023年，星期二最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1→v3→v6和v1→v4→v6V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)第一百三十二页，共一百六十页，编辑于2023年，星期二v1v2v3v4v5v6151617181955402921223041312423(0,s)(15,1)(12,1)(29,1)(40,1)(52,3)第一百三十三页，共一百六十页，编辑于2023年，星期二选址问题

有六个居民点：v1、v2、v3、v4、v5、v6拟修建一所小学，已知各地点的学生人数分别为25、20、30、10、35和45人，其道路如下图所示，试确定学校设于哪一个居民点，才能使学生所走的总路程最少？第一百三十四页，共一百六十页，编辑于2023年，星期二v1v6v5v3v4v22648136137第一百三十五页，共一百六十页，编辑于2023年，星期二D0=027MMM20468M74013MM61016M83103MMM630解:D6=02678112045696401257510148621031195430第一百三十六页，共一百六十页，编辑于2023年，星期二

考虑到各点的学习人数,对D6的每一行乘以相应各点的人数,得到D=050150175200275400801001201801200306015070501001040210703501054954052251801350第一百三十七页，共一百六十页，编辑于2023年，星期二D={1065835535520525750]V1V2V3V4V5V6学校应设在V4点对照D的各元素按列相加,即得到将学校设在不同点时所走的总路程.由C6得到相应路径:V1…..v4:v1—v2—v3---v4V2…..v4:v2—v3---v4V3…..v4:v3---v4V5…..v4:v5---v4V6…..v4:v6—v5---v4第一百三十八页，共一百六十页，编辑于2023年，星期二消防站定位问题

某市有五个火灾易发点v1、v2、v3、v4、v5，现需在其中的一个点处设置消防站，问应设在哪个点才能使消防站的最大服务距离最小。这五个点之间的路网和各段路长如下图所示。第一百三十九页，共一百六十页，编辑于2023年，星期二v1v2v5v3v41142141053243第一百四十页，共一百六十页，编辑于2023年，星期二消防站应设在v3或者v4点第一百四十一页，共一百六十页，编辑于2023年，星期二

有三个仓库运送某种产品到四个市场上去，仓库的供应量和市场的需求量见下表。仓库与市场之间路线上的容量如表所示（容量为零表示两点间无直接的路线可通）。确定现有路线容量是否能满足市场的需求。若不能，应修改哪条线路的容量。网络运输容量问题第一百四十二页，共一百六十页，编辑于2023年，星期二市场仓库供应量需求量20206020A1301004020A200105020A32010405100B1B2B3B4第一百四十三页，共一百六十页，编辑于2023年，星期二解：用点A1A2A3表示三个仓库仓库，点B1、B2、B3、B4表示四个市场。●●●●●●●●●20，2020，20100，5030，2010，040，1010，050，2020，010，1040，405，0SA1A2A3B1B2B3B4T20,2020,1060,4020,20F1=90第一百四十四页，共一百六十页，编辑于2023年，星期二●●●●●●●●●20，2020，20100，7030，510，1040，510，1050，1020，1510，1040，405，5SA1A2A3B1B2B3B4T20,2020,2060,5020,20F1=110网络运输最大流第一百四十五页，共一百六十页，编辑于2023年，星期二分派问题某飞行队有五名正驾驶员和五名副驾驶员。由于种种原因，某些正、副驾驶员不能同机飞行，某些则可以，如下表所示（“*”表示可同机飞行）。每价飞机出航时需正、副驾驶员各一人，问最多能有几架飞机同时出航？应如何安排正、副驾驶员？第一百四十六页，共一百六十页，编辑于2023年，星期二正、副驾驶员同机飞行情况正副B1B2B3B4B5A1