运筹学11-图与网络

1、第十一章 图与网络规划11.1 图与网络的基本概念图与网络的基本概念11.2 树及最小树问题树及最小树问题11.3 最短路问题最短路问题11.4 网络最大流问题网络最大流问题11.5 最小费用最大流问题最小费用最大流问题11.1 图与网络的基本概念图与网络的基本概念n图的概念图的概念 n所谓图，就是顶点和边的集合，点的集合记为所谓图，就是顶点和边的集合，点的集合记为V V，边的集合记为边的集合记为E E，则图可以表示为：，则图可以表示为：G G（V V，E E），），点代表被研究的事物，边代表事物之间的联系，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两因

2、此，边不能离开点而独立存在，每条边都有两个端点。个端点。n在画图时，顶点的位置、边和长短形状都是无关在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。则两个图相同。 图的表示图的表示 ,211e,212e,413e,314e,315e,426e,437e,448e,549e),(),(987654321654321eeeeeeeeeE e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9点与边点与边 n顶点数顶点数 集合集合V中元素的个数，中元素的个数，记作记作p(G)。n边数边数 集合

3、集合E中元素的个数，记中元素的个数，记作作q(G)。n若若e=u,vE，则称，则称u和和v为为e的的端点端点，而称，而称e为为u和和v的的关联边关联边，也称也称u，v与边与边e相相关联关联。n例如图中的图例如图中的图G，p(G)=6，q(G)=9，nv1，v2是是e1和和e2的端点，的端点，e1和和e2都都是是v1和和v2的关联边。的关联边。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9点边关系点边关系n若点若点u和和v与同一条边相与同一条边相关联，则关联，则u和和v为为相邻点相邻点；若两条边若两条边ei和和ej有同一个有同一个端点，则称端点，则称ei与与ej为为相邻相

4、邻边边。n例如在图中例如在图中v1和和v2为相为相邻点，邻点， v1和和v5不相邻；不相邻；e1与与e5为相邻边，为相邻边，e1和和e7不相邻。不相邻。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9简单图简单图n若一条边的两个端点是同一若一条边的两个端点是同一个顶点，则称该边为个顶点，则称该边为环环；又；又若两上端点之间有多于一条若两上端点之间有多于一条边，则称为边，则称为多重边多重边或或平行边平行边。n例如图的例如图的e8为环，为环，e1，e2为两为两重边，重边，e4，e5也是两重边。也是两重边。n含有多重边的图称作含有多重边的图称作多重图多重图。n无环也无多重边的

5、图称作无环也无多重边的图称作简简单图单图。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9图的次图的次n次次 点点v作为边的端点的作为边的端点的次数，记作次数，记作d(v)，如图中，如图中，d(v1)=5, d(v4)=6等等n端点次为奇数的点称作端点次为奇数的点称作奇点奇点；次为偶数的点称；次为偶数的点称作作偶点偶点。n次为次为1的点称为的点称为悬挂点悬挂点，与悬挂点连接的边称作与悬挂点连接的边称作悬挂边悬挂边；n次为次为0的点称为的点称为孤立点孤立点。n图中的点图中的点v5即为悬挂点，即为悬挂点，边边e9即为悬挂边，而点即为悬挂边，而点v6则是弧立点。则是弧立点。 e

6、1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9定理定理 n若图若图G中所有点都是孤中所有点都是孤立点，则称图立点，则称图G为为空图空图。n定理定理1 所有顶点的次的所有顶点的次的和，等于所有边数的和，等于所有边数的2倍。即倍。即 qdV2)(e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9n定理定理2 在任一图中，在任一图中，奇点的个数必为偶数。奇点的个数必为偶数。 n设设V1和和V2分别是图分别是图G中次数为奇数和偶数中次数为奇数和偶数的顶点集合。由定理的顶点集合。由定理1有有 qddVV2)()(21e1 e2 e3 e4 e5v2 v3v1v4

7、v5v6e6e7e8e9链链 n由两两相邻的点及由两两相邻的点及其相关联的边构成其相关联的边构成的点边序列称为的点边序列称为链链。nv0称为链的称为链的起点起点， vn称为链的称为链的终点终点。n若若v0 vn则称该链为则称该链为开链开链，反之称为，反之称为闭闭链链或或回路回路。 nnneee,122110e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9简单链简单链 n若链中所含的边均不若链中所含的边均不相同，则称为相同，则称为简单链简单链；若点均不相同，则称若点均不相同，则称为为初等链初等链或或通路通路。n除起点和终点外点均除起点和终点外点均不相同的闭链，称为不相同的闭

8、链，称为初等回路初等回路或称为或称为圈圈。n例如图中例如图中e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9是一条链，且是开链，也是简单链，但不是初等链，因是一条链，且是开链，也是简单链，但不是初等链，因为为v1出现两次。出现两次。4312211,eee圈圈 n若链中所含的边均不若链中所含的边均不相同，则称为相同，则称为简单链简单链；若点均不相同，则称若点均不相同，则称为为初等链初等链或或通路通路。除。除起点和终点外点均不起点和终点外点均不相同的闭链，称为相同的闭链，称为初初等回路等回路或称为或称为圈圈。n例如图中例如图中e1 e2 e3 e4 e5v2 v3v1v4v5

9、v6e6e7e8e9是一个圈。是一个圈。143746211,eeee连通性连通性 n若一个图若一个图G的任意两点的任意两点之间均至少有一条通之间均至少有一条通路（初等链）连接起路（初等链）连接起来，则称这个图来，则称这个图G是一是一个个连通图连通图，否则称作，否则称作不连通图不连通图。n例如图中，例如图中，v1和和v6之间之间没有通路，因此它不没有通路，因此它不是连通图，而如果去是连通图，而如果去掉掉v6，则构成一个连通，则构成一个连通图。图。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9连通的意义连通的意义 n连通是一个很重要的连通是一个很重要的概念，如果一个问题概

10、念，如果一个问题所对应的图是一个不所对应的图是一个不连通图，则该问题一连通图，则该问题一定可以分解成互不相定可以分解成互不相关的子问题来加以研关的子问题来加以研究，即可以把不连通究，即可以把不连通图分解成连通的子图图分解成连通的子图来研究。来研究。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9子图子图 n子图的定义子图的定义 设，设， G1=(V1,E1), G2=(V2,E2)，如果如果V1 V2 ，又，又E1 E2 ，则称则称G1是是G2的的子图子图。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9e1 e2 e3 e4 e5v2 v3v1必

11、须指出，并不是从图必须指出，并不是从图G2中任选一些顶点和边中任选一些顶点和边在一起就组成在一起就组成G2的子图的子图G1，而只有在，而只有在G2中的一中的一条边以及连接该边的两条边以及连接该边的两个端点均选入个端点均选入G1时，时，G1才是才是G2的子图。的子图。特殊子图特殊子图 n当当G1中不包含中不包含G2中所有中所有的顶点和边，则称的顶点和边，则称G1是是G2的的真子图真子图。n部分图部分图 若若V1=V2，E1 E2 ，则称，则称G1为为G2的的一个一个部分图部分图。 n若若V1 V2 ，nE1= u,v | uV1, vV1，则称，则称G1是是G2中中 由由V1导出的导出的导出子图

12、导出子图。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9e1 e2 e3 e4 e5v2 v3v1有向图有向图n在有些图中，边是没有方向的，即在有些图中，边是没有方向的，即u,v=v,u，这，这种图称为种图称为无向图无向图。n而有些关系是不对称的，例如父子关系、上下级而有些关系是不对称的，例如父子关系、上下级关系、加工工序的先后顺序等都具有单向性，用关系、加工工序的先后顺序等都具有单向性，用图来表示这些关系时，得到的边是具有方向的，图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为用带箭头的线来表示，称为弧弧。n从顶点从顶点u指向指向的弧的弧a，记作，

13、记作a=(u,v),(u,v)(v,u)，其，其中中u称为称为a的起点，的起点，v称为称为a的终点，这样的图称为的终点，这样的图称为有向图有向图。仍以。仍以V表示点的集合，以表示点的集合，以A表示弧的集合，表示弧的集合，则有向图表示为则有向图表示为D（V，A） 有向图例有向图例e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9有向图的链路有向图的链路 n有向图中，在不考虑边的方向有向图中，在不考虑边的方向时，也可以相同地定义时，也可以相同地定义链链，若，若有向图有向图D（V，A）中，）中，P是一是一个从个从u到到v的链，且对的链，且对P中每一条中每一条弧而言，在序列中位于该

14、弧前弧而言，在序列中位于该弧前面的点恰好是其起点，而位于面的点恰好是其起点，而位于该弧后面的点恰好是其终点，该弧后面的点恰好是其终点，这个链这个链P就称为是就称为是D中从中从u到到v的的一条一条路路。n当路的起点与终点相同，即当路的起点与终点相同，即u=v时，称作一条时，称作一条回路回路。n顶点全不相同的路称为顶点全不相同的路称为初等路初等路。n除起点和终点外点均不相同的除起点和终点外点均不相同的回路称为回路称为初等回路初等回路。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e911.2 树及最小树问题树及最小树问题一个没有圈的图称为一个一个没有圈的图称为一个无圈图无圈图

15、或称为或称为林林。一个连通的无圈图则称为一个连通的无圈图则称为树树，一个林的每个连通子图都，一个林的每个连通子图都是一个树。是一个树。定理定理 以下关于树的六种不同描述是等价的：以下关于树的六种不同描述是等价的：n无圈连通图。无圈连通图。n无圈，无圈，q=p-1。n连通，连通，q=p-1。n无圈，但若任意增加一条边，则可得到一个且仅一个圈。无圈，但若任意增加一条边，则可得到一个且仅一个圈。n连通，但若任意舍弃一条边，图便不连通。连通，但若任意舍弃一条边，图便不连通。 n每一对顶点之间有一条且仅有一条链。每一对顶点之间有一条且仅有一条链。部分树部分树 n若若T是图是图G（V，E）的部分图，且）的

16、部分图，且T是树，则称是树，则称T为为G的的部分树部分树。n若若T是图是图G的部分树，则从的部分树，则从G中去掉中去掉T中所有的边，中所有的边，所得到的子图称为所得到的子图称为G中的中的T的的余树余树，也称为，也称为G的一个的一个余树。余树。n余树不一定是树！余树不一定是树！ 一个没有圈的图称为一个一个没有圈的图称为一个无圈图无圈图或称为或称为林林。一个连通的无圈图则称为一个连通的无圈图则称为树树，一个林的每个连通子图，一个林的每个连通子图都是一个树。都是一个树。网络概念网络概念n 图只能用来研究事物之间有没有某种关系，而不能图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。

17、研究这种关系的强弱程度。n 网络网络 赋权的图赋权的图 n 权权 程度的度量，数量描述。程度的度量，数量描述。 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2网络最短树问题网络最短树问题 n最短树问题最短树问题的一般提法是：选取网络中的部分图，的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。使得网络连通，且使总权数最短。n在实际应用中，经常碰到需要求一个赋权连通图的在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。例如，用节点表示城市，用边表示最短树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆可以在两个城市之间架

18、设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。之间均由光缆相通，且使光缆的总长度最短。n求最短树的方法，依据的是树的特点，即无圈和连求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为通，加上最短的要求，方法主要有两种：一种称为破圈法破圈法，一种称为，一种称为生长法生长法 网络最短树网络最短树- -破圈法原理破圈法原理 破圈法原理破圈法原理n如果网络图中无圈并且如果网络图中无圈并且q=p-1，则已经是树；，则已经是树；n如果网络图中有圈，则截去该圈中权数

19、最大的边；这如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个；样，并不影响网络图的连通性，且能使边数减少一个；n经过一定次数的截边，网络图中将再也没有圈，成为经过一定次数的截边，网络图中将再也没有圈，成为无圈图；无圈图；n如果此时的网络满足如果此时的网络满足q=p-1，则已经是树；，则已经是树；n由于每次截去的边在圈中具有最大的权数，因此获得由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。的树也是最短的树。 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2破圈法破圈法步骤步骤在网络图中寻找一个圈，若已经无圈则转在网络

20、图中寻找一个圈，若已经无圈则转。在圈中选取权数最大的边，从网络图中截去该边，在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转对新的网络，转。若若q=p-1q=p-1，则已找到最短树，否则网络图不连通，则已找到最短树，否则网络图不连通，无最短树。无最短树。方法示例：方法示例：例例 对图中的网络，对图中的网络，用破圈法求最短树。用破圈法求最短树。 网络最短树网络最短树- -生长法原理生长法原理 生长法原理生长法原理 类似于自然界中植物生长的过程，结合就近生长和类似于自然界中植物生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到所有的点都已经避免构成圈的要求，逐步生长直到所有的点都已

21、经被包含。被包含。 如果原网络不连通，则在生长过程中会出现某些点如果原网络不连通，则在生长过程中会出现某些点不能被生长，则结束。不能被生长，则结束。 避圈的原理是已经被包含在生长过的树中的点不再避圈的原理是已经被包含在生长过的树中的点不再被生长。被生长。 由于在每次生长时都采用就近生长的方法，生成的由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。树一定是最短树。 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2生长法步骤生长法步骤 从图上任选一点从图上任选一点i，令，令 1iS11SVS若这样的边不存在，则原图没有最短部分树。若这样的边不存在，则原图没有最短部分树

22、。令令 若若S=VS=V，则已找到最，则已找到最短树，否则短树，否则，SSji,1jkkSS1jkkSS从从Sk中的各点到中的各点到Sk中各点的边中选权数最小的中各点的边中选权数最小的边，设为边，设为i，j，则，则生长法示例生长法示例 取取S=v1, 则则S到其余点的距离在距离矩阵中第一行到其余点的距离在距离矩阵中第一行013103930583503698302620654321L v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2v2v3v4v5v6S126v2389S2389013103930583503698302620654321Lv2v3v4v5v6S126v2389

23、S2389v353S353v51S451v63S53 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v211.3 最短路问题最短路问题n最短路问题的一般提法是：欲寻找网络中从起点最短路问题的一般提法是：欲寻找网络中从起点1 1到终点到终点n n的最短路线，即寻求连接这两点的边的总的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。网络，也可以是无向网络。 9757845646547sabcdeft最短路问题的狄克斯拉算法最短路问题的狄克斯拉算法 把把V分成两个集合分成两个集合, 1,

24、321nSiSSjTPj)(0)(1)(),(minijijlPT)(jT)(minjSTj)()(kkTP令令计算计算求求若若vk=vn则已经求得则已经求得vn到到v1的最短路线，否则继续计算的最短路线，否则继续计算 使用条件使用条件 lij0算法解释算法解释 若以若以P(vi)记记v1到到vi的最短距离，则根据动态规划原理应有的最短距离，则根据动态规划原理应有 第一步第一步 取取P(v1)0，而，而T(vj)则是对则是对P(vj)所取的初值；所取的初值；)(min)(iijijPlP v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2SjTPj)(0)(1第二步第二步 利用

25、利用P(vi)已知，据上式对已知，据上式对T(vj)进行修正；进行修正； v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2220 ,)(),()(minlPTminT1212266,0)()()(minl,PTminT13133)(4T)(5T)(6T第三步第三步 对对T(vj)求求 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v22)(2T6)(3T)(4T)(5T)(6T2)()(j2TminP)(minjSTj)()(kkTPk=2, 不是最优，继续不是最优，继续532 , 6)(),()(minlPTminT232331082 ,)(),()(min

26、lPTminT242441192 ,)(),()(minlPTminT25255)(),()(26266lPTminT v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2在所有的在所有的T(vj)中确定最小的中确定最小的 5)(3T10)(4T11)(5T)(6T5)()(3jSTTminj5)()(33TP v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2k=3, 不是最优，继续不是最优，继续1055 ,10)(),()(minlPTminT34344835 ,11)(),()(minlPTminT353555 ,)(),()(minlPTminT36366

27、8)()(5jSTTminj8)()(55TP v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2k=5, 不是最优，继续不是最优，继续108 ,10)(),()(minlPTminT54544918 ,)(),()(minlPTminT565669)()(6jSTTminj9)()(66TP v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2k=6=n, 已经是最优。如果希望计算已经是最优。如果希望计算v1到到v4的最短距离，继续的最短距离，继续 1039 ,10)(),(min)(minlPTT6464410)()(4jSTTminj10)()(44TP v

28、1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2表格实现表格实现013103930583503698302620654321L v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2vjv1v2v3v4v5v6初始值初始值T( vj )0第一次第一次P( )+lij0+2 0+60+0+0+T( )26第二次第二次P( )+lij2+32+82+92+T( )51011第三次第三次P( )+lij5+55+35+T( )108第四次第四次P( )+lij8+ 8+1T( )109福德算法福德算法 jjld1)1 (适用于有负权，但无负回路的有向或无向网络，设适用于有

29、负权，但无负回路的有向或无向网络，设dj(k)为从为从1到到j的边数不超过的边数不超过k的路线中距离最短的。的路线中距离最短的。算法依据的思想是动态规划最优性原理，在此处形成递算法依据的思想是动态规划最优性原理，在此处形成递推公式：推公式： 其算法步骤如下：其算法步骤如下： 令令)1(ij(k)ikjldmind计算计算若对所有若对所有j)()1(kjkjdd则最优，否则把则最优，否则把k的值加的值加1，继续计算。，继续计算。若若k=n-1，则说明存在负回路，最短路线不存在。，则说明存在负回路，最短路线不存在。 min)()1(ijkikjldd福德算法示例福德算法示例 min)()1(ijk

30、ikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L1jjld)1(min)()1(ijkikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620L654321)1(jdi1(1)i(1)1ldmind026min)()1(ijkikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620L654321i1(1)i(2)1ldmind)2(jd026)1(jd025(

31、2)10(2)9(3)i2(1)i(2)2ldmindi3(1)i(2)3ldmindi4(1)i(2)4ldmindi5(1)i(2)5ldmindi6(1)i(2)6ldmindmin)()1(ijkikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620L654321)2(jd620)1(jd025(2)10(2)9(3)ij(2)i(3)jldmind)3(jd)3(jd10(5)8(3)10520ij(3)i(4)jldmind)4(jd0251089(5)5(jdij(4)i(5)jldmind0251089例

32、例 求：求：5 5年内，哪些年初购置新设备，使年内，哪些年初购置新设备，使5 5年内的总费用最年内的总费用最小。小。 解：（解：（1 1）分析：可行的购置方案（更新计划）是很多的，）分析：可行的购置方案（更新计划）是很多的， 如：如： 1 1） 每年购置一台新的，则对应的费用为：每年购置一台新的，则对应的费用为： 11+11+12+12+13 +5+5+5+5+5 = 84 2 ) 2 )第一年购置新的，一直用到第五年年底，则总费第一年购置新的，一直用到第五年年底，则总费用为：用为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。显然不同的方案对应不同的费用。 第第i年

33、度年度 1 2 3 4 5购置费购置费 11 11 12 12 13设备役龄设备役龄 0-1 1-2 2-3 3-4 4-5维修费用维修费用 5 6 8 11 18 （2 2）方法：将此问题用一个赋权有向图来描述，）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。然后求这个赋权有向图的最短路。 求解步骤：求解步骤： 1 1）画赋权有向图：）画赋权有向图： 设设 V Vi i 表示第表示第i i年初，年初，(V(Vi i ,V ,Vj j ) )表示第表示第i i 年初年初购买新设备用到第购买新设备用到第j j年初（年初（j-1j-1年底），而年底），而W Wi ji j 表

34、表示相应费用，则示相应费用，则5 5年的一个更新计划相当于从年的一个更新计划相当于从V V1 1 到到V V6 6的一条路。的一条路。 2 2）求解）求解 （标号法）（标号法） W12 =11+5=16W13 =11+5+6=22W14 =11+5+6+8=30W15 =11+5+6+8+11=41W16 =11+5+6+8+11+18=59 W23 =11+5=16 W24 =11+5+6=22W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6

35、=23W36 =12+5+6+8=31 11.4 网络最大流问题网络最大流问题 所谓最大流问题就是在一定的条件下，要求流过网所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：在最大流问题中一般有如下规定：网络有一个起点网络有一个起点s和一个终点和一个终点t网络是有向网络，即流有方向性。网络是有向网络，即流有方向性。在网络各条弧上都有一个权，表示允许流过的最大在网络各条弧上都有一个权，表示允许流过的最大流量。若以流量。若以bij表示由表示由i到到j的弧上允许流过的最大流的弧上允许流过的

36、最大流量，以量，以xij表示实际流过该弧的流量，则表示实际流过该弧的流量，则0 xij bij网络中，除起点网络中，除起点s和终点和终点t之外的任何顶点，流入量之外的任何顶点，流入量总和应该等于流出量的总和。总和应该等于流出量的总和。 最大流问题的数学模型最大流问题的数学模型ijijjijjjibx0tifs,ti0sifxxs.tfMax vs1011 65 4 7 3 915vt v5 v3 v4 v2最大流最大流- -最小割集定理最小割集定理 最大流最小割集定理揭示了最小割集（网络中的瓶颈）最大流最小割集定理揭示了最小割集（网络中的瓶颈）容量与最大流量的关系，也提供了一个求最大流的方法。

37、容量与最大流量的关系，也提供了一个求最大流的方法。VSSSS Cijjib),(,),( SSCjiji网络网络割集容量割集容量最小割集最小割集 所有割集中容量最小的一个割集。所有割集中容量最小的一个割集。流过网络的最大流量等于最小割集的容量流过网络的最大流量等于最小割集的容量割集割集 vs1011 65 4 7 3 915vt v5 v3 v4 v229(vs v2) (v3 v2) (v3 v4) (v3 v5)v2 v4 v5 vtvs v3.20(vs v3) (v2 v4) (v2 v5)v3 v4 v5 vtvs v224(vs v2) (vs v3)v2 v3 v4 v5 vtv

38、s容量容量割集割集SS福德富克逊方法原理福德富克逊方法原理 算法的原理算法的原理 首先首先,依据最大流问题的要求依据最大流问题的要求,为网络分配一个可行流。为网络分配一个可行流。 所谓可行流所谓可行流,是指所有弧上流量满足容量限制是指所有弧上流量满足容量限制,所有中所有中间点满足平衡条件的流；间点满足平衡条件的流； 若这一可行流的流量就是最大流量，则问题已经解决；若这一可行流的流量就是最大流量，则问题已经解决； 若不是最大流量，则增加流量获得流量更大的可行流。若不是最大流量，则增加流量获得流量更大的可行流。网络中的最大流量网络中的最大流量fmax值大小是由网络中最狭窄处瓶颈的值大小是由网络中最

39、狭窄处瓶颈的容量所决定的。容量所决定的。 福德富克逊方法流图福德富克逊方法流图 求一个初始可行流求一个初始可行流判断初始可行流是否最优判断初始可行流是否最优求使目标得到改善的可行流求使目标得到改善的可行流结结束束是是否否福德富克逊方法讨论福德富克逊方法讨论 若弧若弧(vi,vj)上的流量满足上的流量满足xij=bij，则称该弧为，则称该弧为饱和弧饱和弧，否则，否则称为称为非饱和弧非饱和弧。 若弧若弧(vi,vj)上的流量上的流量xij=0。则称该弧为。则称该弧为零流弧零流弧，否则称为，否则称为非零流弧非零流弧。 一条从一条从s到到t的初等链是由的初等链是由s开始的点、边序列，其中没开始的点、边

40、序列，其中没有相同的点，也不考虑弧的方向。有相同的点，也不考虑弧的方向。 把这条链中的把这条链中的s到到t方向相同的弧称为方向相同的弧称为正向弧正向弧。 把这条链中的把这条链中的s到到t方向相反的弧称为方向相反的弧称为逆向弧逆向弧。在上述的可行流中，从在上述的可行流中，从s到到t的某个初等链满足：的某个初等链满足： 其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。 其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。则称该链为一条则称该链为一条流量增广链流量增广链。 流量增广链流量增广链: 从从s到到t的某个初等链满足的某个初等链满足 其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。

41、其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。结论：若在可行流中，存在从结论：若在可行流中，存在从s到到t的增广链，则该可行的增广链，则该可行流不是最大流，其流量可以增加；否则若不存在从流不是最大流，其流量可以增加；否则若不存在从s到到t的增广链，则该可行流是最大流。的增广链，则该可行流是最大流。 增广链的性质：增广链的性质： Vs到增广链上任一点也有增广链到增广链上任一点也有增广链; 增广链上任一点到增广链上任一点到Vt也有增广链也有增广链;福德富克逊方法步骤福德富克逊方法步骤 为网络分配初始流为网络分配初始流x xijij标在图中弧旁的标在图中弧旁的( )( )内内寻求增广链，若不存

42、在，则已最优寻求增广链，若不存在，则已最优, , 否则否则在增广链上调整流量，产生新的可行流。在增广链上调整流量，产生新的可行流。 重复重复、两步，直到最优。两步，直到最优。寻求增广链的方法寻求增广链的方法 寻求流量增广链的方法，是依据增广链的性质而产生寻求流量增广链的方法，是依据增广链的性质而产生的，其基本思路类似于最短树问题的生长法。的，其基本思路类似于最短树问题的生长法。从从s开始，逐个检查每个点开始，逐个检查每个点i，看是否存在从，看是否存在从s到到i的的增广链。增广链。如果存在从如果存在从s到到i的增广链，的增广链， 而（而（Vi Vj）非饱和或（）非饱和或（Vj Vi）非零流，）非

43、零流，则存在从则存在从V1到到Vj的增广链。的增广链。 福德富克逊方法示例福德富克逊方法示例 为网络分配初始流为网络分配初始流xij标在图中弧旁的标在图中弧旁的( )( )内内 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(1)(5)(7)(5)(8)寻求增广链寻求增广链从从s开始，赋上标记（开始，赋上标记（，），表示），表示s是源点，能够得到是源点，能够得到任意多的量。任意多的量。s称为已标记的点。也表示增广链可以从称为已标记的点。也表示增广链可以从V1延伸到延伸到V1 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3

44、)(1)(5)(7)(5)(8)-, 如果如果vi是已经标记的点是已经标记的点, vj是未标记的点是未标记的点则当则当(vi ,vj)是非饱和弧时是非饱和弧时, vj可以标记可以标记: vi+,ej ej=minei, bij-xij 当当(vj ,vi)是非零流弧时是非零流弧时, vj可以标记可以标记: vi-,ej ej=minei, xji如果如果vt可以标记可以标记,则找到增广链则找到增广链, 否则继续否则继续.如果对于一切未标记的点如果对于一切未标记的点, 均不能再标记均不能再标记, 则已经则已经是最优是最优.如图如图v1是已经标记的点是已经标记的点, 其它点是未标记的点其它点是未标

45、记的点 (v1 ,v2)是非饱和弧是非饱和弧, v2可以标记可以标记: v1+,e2 e2=mine1,b12-x12 (v1 ,v3)是饱和弧是饱和弧, 目前目前v3和其它点暂时不能标记，即和其它点暂时不能标记，即暂时没有从暂时没有从v1 到到v3或其它点的增广链。或其它点的增广链。 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(1)(5)(7)(5)(8)-, vs+, 11如图如图v2是已经标记的点是已经标记的点, v3是未标记的点是未标记的点 (v3 ,v2)是非零流弧是非零流弧, v3可以标记可以标记: v2-,e3 e3=mine2, x32

46、=min11,3-, vs+, 11v2-, 3v2+, 4v3+, 3v5+, 4 vs115 4 315vt v5 v3 v4 v2(4)(9)(1)(5)(7)(5)(8)10 7 9(3) 6vt已经标记已经标记, 找到流量增广链。找到流量增广链。 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(1)(5)(7)(5)(8)-, vs+, 11v2-, 3v2+, 4v3+, 3v5+, 4正向流流量增加正向流流量增加et，逆向流流量减少，逆向流流量减少et 调整后流量调整后流量 f=17 vs10115 4 315vt v5 v3 v4 v2(8

47、)(9)(3)(1)(5)(7)(9)(8)(4) 9 6 7-, vs+, 7v2-, 3v3+, 1v3+, 3v4+, 3vt已经标记已经标记, 找到流量增广链。找到流量增广链。正向流流量增加正向流流量增加et=3，逆向流流量减少，逆向流流量减少et调整后流量调整后流量 f=20 vs10115 4 315vt v5 v3 v4 v2(11)(9)(4)(5)(7)(9)(11)(4) 9 6 7vsv2已经标记，其余点不能标记，已经最优已经标记，其余点不能标记，已经最优最大流量最大流量 fmax=20 vs10115 4 315vt v5 v3 v4 v2(11)(9)(4)(5)(7

48、)(9)(11)(4) 9 6 7-, vs+, 411.5 最小费用最大流问题最小费用最大流问题定义定义 已知网络已知网络G =(V，E，C，d)，f 是是G上的一个可行流，上的一个可行流， 为一条从为一条从vs到到vt的增广链，的增广链， 称为链的费称为链的费用。用。 jijiddfd)(若若 * 是从是从vs到到vt的增广链中费用最小的增广链，则称的增广链中费用最小的增广链，则称 * 是最小费用增广链。是最小费用增广链。结论结论：如果可行流：如果可行流 f在流量为在流量为W(f )的所有可行流中的费的所有可行流中的费用最小，并且用最小，并且 *是关于是关于f 的所有增广链中的费用最小的的所有增广链中的费用最小的增广链，那么沿增广链增广链，那么沿增广链 *调整可行流调