企业运筹学--图与网络理论讲义

《企业运筹学--图与网络理论讲义》由会员分享，可在线阅读，更多相关《企业运筹学--图与网络理论讲义（82页珍藏版）》请在装配图网上搜索。

1、运筹学第五章运筹学第五章图与网络理论 交大管理学院 杨民助图与网络理论图的概念图的概念网络概念网络概念网络最短树问题网络最短树问题网络最短路问题网络最短路问题网络最大流问题网络最大流问题图的概念 什么是图 图的概念图的概念 所谓图，就是顶点和边的集合，点的集合记为所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为边的集合记为E，则图可以表示为：则图可以表示为：G（V，E），），点代表被研究的事物，边代表事点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。在，每条边都有两个端点。在画图时，顶点的位置、边和长短

2、形状都是无在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。的，则两个图相同。图的概念图的概念 图的表示图的表示,211e,212e,413e,314e,315e,426e,437e,448e,549e),(),(987654321654321eeeeeeeeeE e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9图的概念图的概念 点与边点与边 顶点数顶点数 集合集合V中元素的中元素的个数，记作个数，记作p(G)。边数边数 集合集合E中元素的中元素的个数，记作个数，记作q(G)。若若e=

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

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

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

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

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

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

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

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

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

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

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

14、该弧前面的点恰好是其起点，而位于该弧后面的点是其起点，而位于该弧后面的点恰好是其终点，这个链恰好是其终点，这个链P就称为就称为是是D中从中从u到到v的一条的一条路路。当路的起点与终点相同，即当路的起点与终点相同，即u=v时，时，称作一条称作一条回路回路。顶点全不相同的路称为顶点全不相同的路称为初等路初等路。除起点和终点外点均不相同的回路除起点和终点外点均不相同的回路称为称为初等回路初等回路。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9图的概念 树 一个没有圈的图称为一个一个没有圈的图称为一个无圈图无圈图或称为或称为林林。一个连通的无圈图则称为一个连通的无圈图则称为树树

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

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

17、述。v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2网络最短树问题 最短树问题最短树问题的一般提法是：选取网络中的部分图，使的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。得网络连通，且使总权数最短。在实际应用中，经常碰到需要求一个赋权连通图的最在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。例如，用节点表示城市，用边表示可短树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之长度，试求应如何架设光缆，才能使任意两城市之间均由光缆

18、相通，且使光缆的总长度最短。间均由光缆相通，且使光缆的总长度最短。求最短树的方法，依据的是树的特点，即无圈和连通，求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为破圈加上最短的要求，方法主要有两种：一种称为破圈法，一种称为生长法法，一种称为生长法 树的概念回顾 一个没有圈的图称为一个一个没有圈的图称为一个无圈图无圈图或称为或称为林林。一个连通的无圈图则称为一个连通的无圈图则称为树树，一个林的每个连通子图，一个林的每个连通子图都是一个树。都是一个树。定理定理 以下关于树的六种不同描述是等价的：以下关于树的六种不同描述是等价的：无圈连通图。无圈连通图。无圈，

19、无圈，q=p-1。连通，连通，q=p-1。无圈，但增加一条边，则可得到一个且仅有一个圈。无圈，但增加一条边，则可得到一个且仅有一个圈。连通，但若舍弃一条边，图便不连通。连通，但若舍弃一条边，图便不连通。每一对顶点之间有一条且仅有一条链。每一对顶点之间有一条且仅有一条链。网络最短树 破圈法原理 方法原理方法原理如果网络图中无圈并且如果网络图中无圈并且q=p-1，则已经是树；则已经是树；如果网络图中有圈，则截去该圈中权数最大的如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能边；这样，并不影响网络图的连通性，且能使边数减少一个；使边数减少一个；经过一定次数的截边，网络图

20、中将再也没有圈，经过一定次数的截边，网络图中将再也没有圈，成为无圈图；成为无圈图；如果此时的网络满足如果此时的网络满足q=p-1，则已经是树；则已经是树；由于每次截去的边在圈中具有最大的权数，因由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。此获得的树也是最短的树。v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2网络最短树 破圈法 方法步骤方法步骤在网络图中寻找一个圈，若已经无圈则转。在网络图中寻找一个圈，若已经无圈则转。在圈中选取权数最大的边，从网络图中截去该在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转。边，对新的网络，转。若若q=p-1，则已

21、找到最短树，否则网络图不连则已找到最短树，否则网络图不连通，无最短树。通，无最短树。方法示例：方法示例：例例54 对图中对图中的网络，的网络，用破用破圈法求最短树。圈法求最短树。网络最短树 生长法原理 方法原理方法原理 类似于自然界中植物生长的过程，结合就近类似于自然界中植物生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到生长和避免构成圈的要求，逐步生长直到所有的点都已经被包含。所有的点都已经被包含。如果原网络不连通，则在生长过程中会出现如果原网络不连通，则在生长过程中会出现某些点不能被生长某些点不能被生长，则结束。，则结束。避圈的原理是已经被包含在生长过的树中的避圈的原理是已经被包含

22、在生长过的树中的点不再被生长。点不再被生长。由于在每次生长时都采用就近生长的方法，由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。生成的树一定是最短树。v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2网络最短树 生长法1 方法步骤方法步骤 从图上任选一点从图上任选一点i，令令 从从Sk中的各点到中的各点到Sk中各点的边中选权数最小的中各点的边中选权数最小的边，设为边，设为i，j，则则1iS11SVS若这样的边不存在，则原图没有最短部分树。若这样的边不存在，则原图没有最短部分树。令令 若若S=V，则已找到则已找到最短树，否则，最短树，否则，SSji,1jkkSS1j

23、kkSS v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2网络最短树 生长法2 方法示例方法示例取取S=v1,则则S到其余点的距离在距离矩阵中第一行到其余点的距离在距离矩阵中第一行013103930583503698302620654321Lv2v3v4v5v6S126V2389S2389网络最短树 生长法3 方法示例013103930583503698302620654321Lv2v3v4v5v6S126V2389S2389V353S353V51S451V63S53网络最短树 生长法4 v2v3v4v5v6S126V2389S2389V353S353V51S451V63S5

24、3 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2网络最短路线问题 最短路线问题的一般提法是：欲寻找网络中从起点最短路线问题的一般提法是：欲寻找网络中从起点1到终点到终点n的最短路线，即寻求连接这两点的边的总的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。网络，也可以是无向网络。adbetcfs9757845646547图4-7最短路问题的狄克斯拉算法 把把V分成两个集合分成两个集合,1,321nSiSSjTPj)(0)(1)(),(minijijlPT)(jT)(minjS

25、Tj)()(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狄克斯拉算法1狄克斯拉 算法2 算法解释算法解释第二步第二步 利用利用P(vi)已知，据上式对已知，据上式对T

26、(vj)进行修正；进行修正；v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2)(),(minijijlPTSjTPj)(0)(1)(),(min)(12122lPTT 220,min)(),(min)(13133lPTT 660,min)(4T)(5T)(6T狄克斯拉算法3 算法解释算法解释第三步第三步 对对T(vj)求求 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2)(),(minijijlPTSjTPj)(0)(12)(2T6)(3T)(4T)(5T)(6T)(minjSTj)()(kkTP2)(min)(2jTP狄克斯拉算法4 算法解释算法解释k=

27、2,不是最优，继续不是最优，继续)(),(minijijlPTSjTPj)(0)(1 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2)(),(min)(23233lPTT532,6min)(),(min)(24244lPTT1082,min)(),(min)(25255lPTT1192,min)(),(min)(26266lPTT)(minjSTj)()(kkTP狄克斯拉算法5 算法解释算法解释在所有的在所有的T(vj)中确定最小的中确定最小的 )(),(minijijlPTSjTPj)(0)(1)(minjSTj)()(kkTP v1 1 3 9 5 3 83 6 2v6

28、 v5 v3 v4 v25)(3T10)(4T11)(5T)(6T5)()(min3TTjSj5)()(33TP狄克斯拉算法6 算法解释算法解释k=3,不是最优，继续不是最优，继续)(),(minijijlPTSjTPj)(0)(1 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2)(),(min)(34344lPTT1055,10min)(),(min)(35355lPTT835,11min)(),(min)(36366lPTT5,min8)()(min5TTjSj8)()(55TP)(minjSTj)()(kkTP狄克斯拉算法7 算法解释算法解释k=5,不是最优，继续不是

29、最优，继续)(),(minijijlPTSjTPj)(0)(1)(minjSTj)()(kkTP v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2)(),(min)(54544lPTT108,10min)(),(min)(56566lPTT918,min9)()(min6TTjSj9)()(66TP狄克斯拉算法8 算法解释算法解释k=6=n,已经是最优。如果希望计算已经是最优。如果希望计算v1到到v4的最短距离，继续的最短距离，继续 )(),(minijijlPTSjTPj)(0)(1)(minjSTj)()(kkTP1039,10min)(),(min)(64644lPTT

30、10)()(min4TTjSj10)()(44TP v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2狄克斯拉算法9 表格实现表格实现013103930583503698302620654321Lvjv1v2v3v4v5v6初始值初始值T(vj)0 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2第一次第一次P()+lij0+2 0+6 0+0+0+T()26狄克斯拉算法10 表格实现表格实现vjv1v2v3v4v5v6初始值初始值T(vj)0第一次第一次P()+lij0+2 0+6 0+0+0+T()26第二次第二次P()+lij2+3 2+82+92+T(

31、)51011第三次第三次P()+lij5+55+35+T()108第四次第四次P()+lij8+8+1T()109福德算法1 适用于有负权，但无负回路的有向或无向网络，适用于有负权，但无负回路的有向或无向网络，其算法步骤如下：其算法步骤如下：令令jjld1)1(min)()1(ijkikjldd计算计算若对所有若对所有j)()1(kjkjdd则最优，否则把则最优，否则把k的值加的值加1，继续计算。，继续计算。若若k=n-1，则说明存在负回路，最短路线不存在。则说明存在负回路，最短路线不存在。福德算法2 适用于有负权，但无负回路的有向或无向网络，适用于有负权，但无负回路的有向或无向网络，算法中算

32、法中dj(k)为从为从1到到j的边数不超过的边数不超过k的路线中距的路线中距离最短的。离最短的。算法依据的思想是动态规划最优性原理，在此处算法依据的思想是动态规划最优性原理，在此处形成递推公式。形成递推公式。min)()1(ijkikjldd福德算法3 算法示例算法示例 min)()1(ijkikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L1jjld)1(福德算法4 min)()1(ijkikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v201310393058350369

33、8302620654321L)1(jd026福德算法5 min1)1()2(1iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd福德算法6 min2)1()2(2iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2福德算法7 min3)1()2(3iildd v1 1 3 9 5 3 83 6

34、2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 25福德算法8 min4)1()2(4iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510福德算法9 min5)1()2(5iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026

35、)2(jd0min)()1(ijkikjldd2 25109福德算法10 min6)1()2(6iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 25109)3(jd福德算法11 min)2()3(ijijldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510902510810)3(jd

36、福德算法12 min)3()4(ijijldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510902510810)4(jd0251089)3(jd福德算法13 min)4()5(ijijldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510902510810)4(jd0251089)5(

37、jd0251089最大流问题的概念最大流问题的概念所谓最大流问题就是在一定的条件下，要求流过网络的所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：问题中一般有如下规定：网络有一个起点网络有一个起点s和一个终点和一个终点t网络是有向网络，即流有方向性。网络是有向网络，即流有方向性。在网络各条弧上都有一个权，表示允许流过的最大流在网络各条弧上都有一个权，表示允许流过的最大流量。若以量。若以bij表示由表示由i到到j的弧上允许流过的最大流量，的弧上允许流过的最大流量，以以xij表示实

38、际流过该弧的流量，则表示实际流过该弧的流量，则0 xij bij网络中，除起点网络中，除起点s和终点和终点t之外的任何顶点，流入量之外的任何顶点，流入量总和应该等于流出量的总和。总和应该等于流出量的总和。最大流问题的数学模型最大流问题的数学模型最大流最大流问题的问题的数学模型：数学模型：ijijjijjjibxtiftsisifxxtsf0,0.max vs1011 65 4 7 3 915vt v5 v3 v4 v2最大流最小割集定理最大流最小割集定理1 网络中的最大流量网络中的最大流量fmax值大小是由网络值大小是由网络中最狭窄处瓶颈的容量所决定的。中最狭窄处瓶颈的容量所决定的。最大流最小

39、割集定理揭示了最小割集（网络中的瓶颈最大流最小割集定理揭示了最小割集（网络中的瓶颈）容量与最大流量的关系，也提供了一个求最大流的方）容量与最大流量的关系，也提供了一个求最大流的方法。法。割集割集 VSSSS Cijjib),(,),(SSCjiji网络网络割集容量割集容量最小割集最小割集 所有割集中容量最小的一个割集。所有割集中容量最小的一个割集。最大流最小割集定理最大流最小割集定理2 网络中的最大流量网络中的最大流量fmax值大小是由网络值大小是由网络中最狭窄处瓶颈的容量所决定的。中最狭窄处瓶颈的容量所决定的。VSSSS Cijjib),(,),(SSCjiji网络网络割集容量割集容量最小割

40、集最小割集 所有割集中容量最小的一个割集。所有割集中容量最小的一个割集。最大流最小割集定理最大流最小割集定理流过网络的最大流量等于最小割集的容量。流过网络的最大流量等于最小割集的容量。最大流最小割集定理最大流最小割集定理3 vs 1011 65 4 7 3 915vt v5 v3 v4 v2SS割集割集容量容量vsv2 v3 v4 v5 vt(vs v2)(vs v3)24vs v2v3 v4 v5 vt(vs v3)(v2 v4)(v2 v5)20vs v3v2 v4 v5 vt(vs v2)(v3 v2)(v3 v4)(v3 v5)29.福德富克逊方法原理福德富克逊方法原理 算法的原理算法

41、的原理首先，依据最大流问题的要求，为网络分配首先，依据最大流问题的要求，为网络分配一个可行流。所谓可行流，是指所有弧上流一个可行流。所谓可行流，是指所有弧上流量满足容量限制量满足容量限制，所有中间点满足平衡条件所有中间点满足平衡条件的流；的流；若这一可行流的流量就是最大流量，则问题若这一可行流的流量就是最大流量，则问题已经解决；已经解决；若不是最大流量，则增加流量获得流量更大若不是最大流量，则增加流量获得流量更大的可行流。的可行流。福德富克逊方法流图福德富克逊方法流图 求一个初始可行流求一个初始可行流 是是 判断初始可行流是否最优判断初始可行流是否最优 结结 束束 不是不是 求使目标得到改善的

42、可行流求使目标得到改善的可行流福德富克逊方法图示福德富克逊方法图示 算法原理图示算法原理图示初始流初始流初始流初始流福德富克逊方法讨论福德富克逊方法讨论 若弧若弧(vi,vj)上的流量满足上的流量满足xij=bij，则称该弧为则称该弧为饱和弧饱和弧，否则称为否则称为非饱和弧非饱和弧。若弧若弧(vi,vj)上的流量上的流量xij=0。则称该弧为则称该弧为零流弧零流弧，否则，否则称为称为非零流弧非零流弧。一条从一条从s到到t的初等链是由的初等链是由s开始的点、边序列，其开始的点、边序列，其中没有相同的点，也不考虑弧的方向。中没有相同的点，也不考虑弧的方向。把这条链中的把这条链中的s到到t方向相同的

43、弧称为方向相同的弧称为正向弧正向弧。把这条链中的把这条链中的s到到t方向相反的弧称为方向相反的弧称为逆向弧逆向弧。在上述的可行流中，从在上述的可行流中，从s到到t的某个初等链满足：的某个初等链满足：其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。则称该链为一条则称该链为一条流量增广链流量增广链。福德富克逊方法讨论福德富克逊方法讨论 流量增广链流量增广链:从从s到到t的某个初等链满足的某个初等链满足 其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。结论：若在可行流中，存在从结论：若在可

44、行流中，存在从s到到t的增广链的增广链，则该可行流不是最大流，其流量可以增加，则该可行流不是最大流，其流量可以增加；否则若不存在从；否则若不存在从s到到t的增广链，则该可行的增广链，则该可行流是最大流。流是最大流。增广链的性质增广链的性质 流量增广链流量增广链:从从s到到t的某个初等链满足的某个初等链满足 其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。增广链的性质：增广链的性质：1 Vs到增广链上任一点也有增广链到增广链上任一点也有增广链;2 增广链上任一点到增广链上任一点到Vt也有增广链也有增广链;福德富克逊方法步骤福德富克逊方法步骤

45、 算法的步骤算法的步骤：为网络分配初始流为网络分配初始流xij标在图中弧旁的标在图中弧旁的()内内寻求增广链，若不存在，则已最优寻求增广链，若不存在，则已最优,否则否则在增广链上调整流量，产生新的可行流。在增广链上调整流量，产生新的可行流。重复、两步，直到最优。重复、两步，直到最优。寻求增广链的方法寻求增广链的方法 寻求流量增广链的方法，是依据增广链的性寻求流量增广链的方法，是依据增广链的性质而产生的，其基本思路类似于最短树问题质而产生的，其基本思路类似于最短树问题的生长法。的生长法。从从s开始，逐个检查每个点开始，逐个检查每个点i，看是否存在从，看是否存在从s到到i的增广链。的增广链。如果存

46、在从如果存在从s到到i的增广链，的增广链，而（而（Vi Vj）非饱和或（）非饱和或（Vj Vi）非零流，）非零流，则存在从则存在从V1到到Vj的增广链。的增广链。福德富克逊方法示例福德富克逊方法示例 标记化算法的步骤标记化算法的步骤：为网络分配初始流为网络分配初始流xij标在图中弧旁的标在图中弧旁的()内内 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(1)(5)(7)(5)(8)福德富克逊方法示例福德富克逊方法示例 寻求增广链寻求增广链从从s开始，赋上标记（，开始，赋上标记（，），表示），表示s是源点是源点，能够得到任意多的量。，能够得到任意多的量。s

47、称为已标记的点。称为已标记的点。也表示增广链可以从也表示增广链可以从V1延伸到延伸到V1 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(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可以标记可以标记,则找到增广链

48、则找到增广链,否则继续否则继续.如果对于一切未标记的点如果对于一切未标记的点,均不能再标记均不能再标记,则已则已经是最优经是最优.福德富克逊方法示例福德富克逊方法示例 寻求增广链寻求增广链如图如图v1是已经标记的点是已经标记的点,其它点是未标记的点其它点是未标记的点 (v1,v2)是非饱和弧是非饱和弧,v2可以标记可以标记:v1+,e2 e2=mine1,b12-x12 (v1,v3)是饱和弧是饱和弧,目前目前v3和其它点暂时不能标和其它点暂时不能标记，即暂时没有从记，即暂时没有从v1 到到v3或其它点的增广链。或其它点的增广链。vs10115 6 4 7 3 915vt v5 v3 v4 v

49、2(4)(9)(3)(1)(5)(7)(5)(8)-,vs+,11福德富克逊方法示例福德富克逊方法示例 寻求增广链寻求增广链如图如图v2是已经标记的点是已经标记的点,v3是未标记的点是未标记的点 (v3,v2)是非零流弧是非零流弧,v3可以标记可以标记:v2-,e3 e3=mine2,x32=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)6福德富克逊方法示例福德富克逊方法示例 在增广链上调整流量。在增广链上调整流量。vt已经标记已经标记,找到流量增广链。找到流

50、量增广链。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)(9)(3)(1)(5)(7)(9)(8)(4)9 6 7-,vs+,7v2-,3v3+,1v3+,3v4+,3vt已经标记已经标记,找到流量增广链。找到流量增广链。福德富克逊方法示例福德富克逊方法示例

51、在增广链上调整流量。在增广链上调整流量。正向流流量增加正向流流量增加et=3，逆向流流量减少逆向流流量减少et调整后流量调整后流量 f=20 vs10115 4 315vt v5 v3 v4 v2(11)(9)(4)(5)(7)(9)(11)(4)9 6 7福德富克逊方法示例福德富克逊方法示例 寻求增广链寻求增广链Vsv2已经标记，其余点不能标记，已经最优已经标记，其余点不能标记，已经最优最大流量最大流量 fmax=20 vs10115 4 315vt v5 v3 v4 v2(11)(9)(4)(5)(7)(9)(11)(4)9 6 7-,vs+,4福德富克逊方法图示福德富克逊方法图示 算法原理图示算法原理图示初始流初始流初始流初始流图与网络理论作业图与网络理论作业 作业作业P2185-2 5-4