运筹学-图与网络分析.pptx

第第8章图与网络分析章图与网络分析图与网络模型Graph Theory引言引言 十八世纪的哥尼斯堡城中流过一条河（普雷十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有格尔河），河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。ABCD图与网络模型Graph Theory引言引言 “哥尼斯堡哥尼斯堡 7 桥桥”难题最终在难题最终在 1736 年由数学家年由数学家 Euler 的一篇论文的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到的发展是缓慢的，直到 1936 年匈牙利数学家年匈牙利数学家 O.Knig写出了写出了图论的图论的第一本专著第一本专著有限图与无限图的理论有限图与无限图的理论。在图论的发展过程中还有两位著名科学家值得一提，他们是在图论的发展过程中还有两位著名科学家值得一提，他们是克希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出克希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究。行计数时推动了图论中树的计数问题的研究。图论的历史上最具有传奇色彩的问题也许要数著名的图论的历史上最具有传奇色彩的问题也许要数著名的“四色四色猜想猜想”了了历史上许许多多数学猜想之一。它描述对一张地图着色历史上许许多多数学猜想之一。它描述对一张地图着色的问题，曾经有一位数学家这样说：的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白这一问题，但是，两人都无能为力。人都明白这一问题，但是，两人都无能为力。”幸运的是在幸运的是在 1970s 终终于由美国的于由美国的两位数学家借助大型计算机将其证明了。两位数学家借助大型计算机将其证明了。图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念 图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正如图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正如一位数学家所说：一位数学家所说：“可以说，图论为任何一个可以说，图论为任何一个包含了某种二元关系包含了某种二元关系的的系统提供了一种分析和描述的模型。系统提供了一种分析和描述的模型。”下面我们来看一个案例下面我们来看一个案例 国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：是各办事处已订购机票的详细情况表：图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念各办事处已订购机票情况表各办事处已订购机票情况表成都成都重庆重庆武汉武汉上海上海西安西安郑州郑州沈阳沈阳昆明昆明广州广州北京北京成都成都 重庆重庆 武汉武汉 上海上海 西安西安 郑州郑州 沈阳沈阳 昆明昆明 广州广州 北京北京10 5 15 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10 8 2 6 10 图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念 将此问题通过图的模型描述：将此问题通过图的模型描述：下图中，点下图中，点各城市，带箭头连线各城市，带箭头连线从箭尾城市到箭头城市已订从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字购有机票，带箭头连线旁的数字机票数量。机票数量。成成重重武武昆昆上上广广西西郑郑沈沈京京8郑州办事处已订郑州办事处已订有的到北京的有的到北京的机票数量。机票数量。图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念一、一、图及其分类和术语图及其分类和术语 1、图论中所研究的图并非几何学中的图，也不是绘画中的图。在这图论中所研究的图并非几何学中的图，也不是绘画中的图。在这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，也就是说我们研究的是某个系统中的元素也就是说我们研究的是某个系统中的元素点，以及这些元素之间点，以及这些元素之间的某种关系的某种关系连线。连线。定义：定义：图图一个图一个图G是一个有序二元组（是一个有序二元组（V，E），记为），记为G=（V，E）其中（其中（1）V是一个有限非空的集合，其元素称为是一个有限非空的集合，其元素称为G的点或顶点，而称的点或顶点，而称V为为G的点集的点集 V=v1，v2，vn；（；（2）E是是V中元素的无序对中元素的无序对(vi，vj)所构成的一个集合，其元素称为所构成的一个集合，其元素称为G的边，一般表示为的边，一般表示为 e=(vi，vj)，而称，而称E是是G的边集。的边集。边（无向边）边（无向边）没有方向的连线没有方向的连线弧（有向边）弧（有向边）带有方向的连线带有方向的连线无向图无向图 有向图有向图 简单图简单图 多重图多重图完全图完全图 二部图（偶图，双图）二部图（偶图，双图）图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念子图子图 真子图真子图生成子图生成子图 点生成子图点生成子图 边生成子图边生成子图点的次点的次 奇次点奇次点 偶次点偶次点链链 圈圈 路路 回路回路 赋权图赋权图2、连通图连通图 在众多各类图中有一类在实际应用中占有重要地位的图在众多各类图中有一类在实际应用中占有重要地位的图 连通图连通图在图中，任意两点间至少存在着一条链在图中，任意两点间至少存在着一条链连通图连通图不连通图不连通图图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念3、图与矩阵图与矩阵 在图与网络分析的应用中，将面临一个问题在图与网络分析的应用中，将面临一个问题如何分析、计算如何分析、计算一个较大型的网络，这当然需借助快速的计算工具一个较大型的网络，这当然需借助快速的计算工具计算机。那么，计算机。那么，如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有图的矩阵表示也根据所关心的问题不同而有邻接矩阵、关联矩阵、邻接矩阵、关联矩阵、权矩阵等。权矩阵等。邻接矩阵邻接矩阵对于图对于图G=（V，E），），|V|=n，|E|=m，有，有n n阶方阶方矩矩阵阵A=（aij）n n，其中其中 aij=k 当且仅当当且仅当vi与与vj之间有条边时之间有条边时 0 其它其它图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念邻接矩阵邻接矩阵A=（aij）n n=0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 2 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 10 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 2 0 1 0 0 0 v1v2v3v4v5v6v7v8v1 v2 v3 v4 v5 v6 v7 v8 v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念关联矩阵关联矩阵对于图对于图G=（V，E），），|V|=n，|E|=m，有，有m n阶阶矩阵矩阵M=（mij）m n，其中其中 mij =2 当且仅当当且仅当 vi是边是边ej 的两个端点的两个端点 1 1 当且仅当当且仅当 vi是边是边ej 的一个端点的一个端点例例 0 0 其它其它v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8M=（mij）=1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 图与网络模型Graph Theory最小树问题最小树问题二、二、树（树（Tree）和最小树）和最小树 树是图论中一类重要的图，实际中有很多系统的结构都是树。树是图论中一类重要的图，实际中有很多系统的结构都是树。树树连通且不含圈的图，简记为连通且不含圈的图，简记为 T。下面的说法是等价的：下面的说法是等价的：T是一个树。是一个树。T无圈，且无圈，且 m=n-1。T连通，且连通，且 m=n-1。T无圈，但每加一条新的边即出现唯一一个圈。无圈，但每加一条新的边即出现唯一一个圈。T连通，但连通，但每舍去一条边就不连通。每舍去一条边就不连通。T中任意两点，有唯一的一条链相连。中任意两点，有唯一的一条链相连。T是边数最少的是边数最少的连通图。连通图。图的生成树图的生成树若若G图的一个点图的一个点生成子图是一个树，则称此树是生成子图是一个树，则称此树是G图的图的一个一个生成树。生成树。树的权树的权若若Tk是加权图是加权图G的一棵树，则树的一棵树，则树T的全部边的权之和称为树的全部边的权之和称为树Tk的权，记为的权，记为 （Tk）=（e）；）；e Tk最小树最小树T*是加权图是加权图G的一棵的一棵最小最小树，即树，即（T*）=min (Tk)k图与网络模型Graph Theory最小树问题最小树问题破圈法，避圈法求破圈法，避圈法求生成树：生成树：图图G生成树生成树T生成树生成树T图与网络模型Graph Theory最小树问题最小树问题破圈法，避圈法求最小破圈法，避圈法求最小生成树：生成树：图图G生成树生成树T生成树生成树T15424531344215121231211212312112图与网络模型Graph Theory最短路问题最短路问题三、三、路（路（Path）和最短路）和最短路 最短路问题是网络分析中应用最广泛的问题之一。尽管前面最短路问题是网络分析中应用最广泛的问题之一。尽管前面介绍了用动态规划方法求解，但有时却较困难，此时图论的方法却十介绍了用动态规划方法求解，但有时却较困难，此时图论的方法却十分有效。分有效。最短路问题的一般描述：最短路问题的一般描述：G=（V，E）是连通图，图中各边（）是连通图，图中各边（vi，vj）有权有权lij（=表示表示vi，vj间间无边无边），），vs、vt为为图中任意两指定点，求一条路图中任意两指定点，求一条路 ，使其是从，使其是从 vs到到 vt的所有路中最短（路中各边的权之和最小）的一条路。即的所有路中最短（路中各边的权之和最小）的一条路。即L（）=min lij（vi，vj）图与网络模型Graph Theory最短路问题最短路问题 E.W.Dijkstra 算法（标号算法）算法（标号算法）算法基本思路分析：（逐步向外搜索）算法基本思路分析：（逐步向外搜索）52165828997221210X（P标号）标号）Y（T标号）标号）起点到起点到该点的该点的最短距最短距离离起点到起点到该点的该点的最短距最短距离的离的上上界界2527 5111212105756 679 910106 3 3人、狼、羊、草渡河游戏人、狼、羊、草渡河游戏一个人带着一条狼、一只羊、一筐白菜过河蛤由于船太小，人一次只能带一样东西乘船过河。狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉。人人 M（Man），），狼狼 W（Wolf），），羊羊 G（Goat），草），草 H（Hay）。）。点点 vi 表示河岸的状态，表示河岸的状态，边边 ek 表示由状态表示由状态 vi 经一次渡河到状态经一次渡河到状态 vj，权权边边 ek 上的权定为上的权定为 1 1。我们可以得到下面的加权有向图：我们可以得到下面的加权有向图：图与网络模型Graph Theory最短路问题最短路问题v1，u1 =（M，W，G，H）；）；v2，u2=（M，W，G）；）；v3，u3 =（M，W，H）；）；v4，u4 =（M，G，H）；）；v5，u5 =（M，G）。）。此游戏转化为在下面的二部图中求从此游戏转化为在下面的二部图中求从 v1 到到 u1 的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1图与网络模型Graph Theory最短路问题最短路问题 在在 E.W.Dijkstra 算法中必须满足一个条件算法中必须满足一个条件 在图在图 G 中所有边的权中所有边的权 lij 0。若在图。若在图 G 中存在中存在有负权边（有负权边（当然，这种情形只针对有向图而言当然，这种情形只针对有向图而言）时）时必须对必须对E.W.Dijkstra 算法加以修改算法加以修改 称为修改称为修改的的 E.W.Dijkstra 算法。算法。2、情况二：、情况二：wij0设从设从V1到到Vj(j=1,2,t)的最短路长为的最短路长为P1jV1到到Vj无任何中间点无任何中间点 P1j（1）=wijV1到到Vj中间最多经过一个点中间最多经过一个点 P1j（2）=min P1j（1）+wijV1到到Vj中间最多经过两个点中间最多经过两个点 P1j（3）=min P1j（2）+wij.V1到到Vj中间最多经过中间最多经过t-2个点个点 P1j（t-1）=min P1j（t-2）+wij终止原则：终止原则：1）当）当P1j（k）=P1j（k+1）可停止，最短路可停止，最短路P1j*=P1j（k）2）当）当P1j（t-1）=P1j（t-2）时，再多迭代一次时，再多迭代一次P1j（t），若，若P1j（t）=P1j（t-1），则原问题无解，存在负回路。，则原问题无解，存在负回路。例：例：求下图所示有向图中从求下图所示有向图中从v1到各点的到各点的最短路。最短路。v1v4v2v3v5v6v7v825-34674-23-1-342 wij d(t)(v1,vj)v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v80 25-30-2406400-3 0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-336910020-336910说明：表中空格处为说明：表中空格处为+。4例例 设备更新问题设备更新问题制订一设备更新问题，使得总费用最小制订一设备更新问题，使得总费用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 购买费购买费 13 14 16 19 24 使用年数使用年数 0-1 1-2 2-3 3-4 4-5 维修费维修费 8 10 13 18 27 解解设以设以vi(i=1,2,3,4,5)表示表示“第第i年初购进一台年初购进一台新设备新设备”这种状态，以这种状态，以v6表示表示“第第5年末年末”这种状态；这种状态；以弧以弧(vi,vj)表示表示“第第i年初购置的一台设备一直使用到年初购置的一台设备一直使用到第第j年初年初”这一方案，以这一方案，以wij表示这一方案所需购置费表示这一方案所需购置费和维护费之和。和维护费之和。v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31,V1)(44,V1)(62,V1)(78,V3)这样，可建立本例的网络模型。于是，该问题就这样，可建立本例的网络模型。于是，该问题就可归结为从图中找出一条从可归结为从图中找出一条从v1到到v6的最短路问题。的最短路问题。用用Dijkstra标号法，求得最短路为标号法，求得最短路为 v1v3v6 即第一年初购置的设备使用到第三年初予以更新，即第一年初购置的设备使用到第三年初予以更新，然后一直使用到第五年末。这样五年的总费用最然后一直使用到第五年末。这样五年的总费用最少，为少，为78。图与网络模型Graph Theory距离矩阵摹乘法距离矩阵摹乘法Dijkstra算法比较简单，但是，对于含有负权弧的网络可能失效。算法比较简单，但是，对于含有负权弧的网络可能失效。这时，应对算法加以修改，即所谓这时，应对算法加以修改，即所谓“修改的修改的 Dijkstra 算法算法”。下面，。下面，介绍一种算法介绍一种算法距离矩阵摹乘法，它适用于任何网络的最短路问题。距离矩阵摹乘法，它适用于任何网络的最短路问题。例如例如v1v3v4v2v6v534233-24411-16333图与网络模型Graph Theory距离矩阵摹乘法距离矩阵摹乘法1、网络的距离矩阵、网络的距离矩阵设一网络设一网络N中有中有n个点，其中任意两点个点，其中任意两点 vi 与与 vj 之间都有一条边之间都有一条边 (vi,vj)，其权数为，其权数为 wij -。若。若 vi 与与 vj 不相邻，则虚设一条边不相邻，则虚设一条边(vi,vj)，并令其权数并令其权数wij=。距离矩阵距离矩阵 W=（wij）前例中的距离矩阵为前例中的距离矩阵为W=v1 v2 v3 v4 v5 v6v1 0 3 2 4v2 0 4 4 1v3 0 -1 6 v4 3 -2 0 1 v5 5 0 3v6 3 3 0图与网络模型Graph Theory距离矩阵摹乘法距离矩阵摹乘法2、求各点至某点的最短路、求各点至某点的最短路求求 vi（i=1,2,n）至某点）至某点 vr 的最短路。的最短路。令：令：dir(k)=vi 走走k步达到步达到 vr 的最短距离，的最短距离，i=1,2,n则有则有 dir(1)=wir,i=1,2,ndir(k)=min wij+djr(k-1),i=1,2,n1jn令：令：dk =（d1r(k),d2r(k),dnr(k),）T ,k=1,2,图与网络模型Graph Theory距离矩阵摹乘法距离矩阵摹乘法矩阵摹乘运算法：矩阵摹乘运算法：dk=W dk-1 ,(k=2,3,)当当 dk=dk-1,(k=2,3,)则计算停止，则计算停止，dk 中的元素即为各点到中的元素即为各点到 vr 的最短距离。的最短距离。图与网络模型Graph Theory网络中心和重心问题网络中心和重心问题一、一、基本概念基本概念 网络最短距离矩阵网络最短距离矩阵 D=(dij)nn dij表示表示vi到到vj的最短距离的最短距离（1）网络的中心）网络的中心令：令：d(vi)=max dij ,i=1,2,n若若 max d(vi)=d(vk)1in1jn则称点则称点 vk 为网络的中心。为网络的中心。图与网络模型Graph Theory网络中心和重心问题网络中心和重心问题（2）网络的重心）网络的重心 设设 gi 为点为点 vi 的权重（的权重（i=1,2,n），），令：令：h(vj)=gidij ,j=1,2,ni=1n若若 max h(vj)=h(vr)1jn则称点则称点 vr 为网络的重心。为网络的重心。图与网络模型Graph Theory网络中心和重心问题网络中心和重心问题二、二、应用应用例例 某地某地 7 个村镇之间的现有交通道路如下图，边旁数值为各村个村镇之间的现有交通道路如下图，边旁数值为各村镇之间道路的长度，点旁数值为各村镇的小学生人数。现拟在某一村镇镇之间道路的长度，点旁数值为各村镇的小学生人数。现拟在某一村镇建一商店和小学，试问：建一商店和小学，试问：（1）商店应该建在何村，能使各村都离它较近？）商店应该建在何村，能使各村都离它较近？（2）小学应该建在何村，能使各村小学生总的行走路程最短？）小学应该建在何村，能使各村小学生总的行走路程最短？图与网络模型Graph Theory网络中心和重心问题网络中心和重心问题v1v3v4v5v6v7v2746435712324230404535252050距离距离人数人数图与网络模型Graph Theory网络中心和重心问题网络中心和重心问题（1）中心问题）中心问题 网络最短距离矩阵如下：网络最短距离矩阵如下：vj viD=(dij)d(vi)=max dij 123456710345781010230324577343055688452502355(min)57452013768563102871078532010j结论：结论：商店应该建在商店应该建在 v4 村。村。图与网络模型Graph Theory网络中心和重心问题网络中心和重心问题（2）重心问题）重心问题 vj vi gidij123456710120160200280320400275075501001251753180135022522527036041506015006090150514080100400206062801752101053507075003504002501501000h(vj)13259201095870850(min)9251215结论：结论：小学应该建在小学应该建在 v5 村。村。第四节第四节 最大流问题最大流问题 如下是一运输网络，弧上的数字表示每条弧上的容量，问：如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？该网络的最大流量是多少？vsv2v1v3v4vt432312234图与网络模型Graph Theory网络流问题网络流问题定义定义1：定一个有向图：定一个有向图D=(V,E),在在V中有一个发点中有一个发点vs和一收点和一收点vt，其余，其余的点为中间点。对于每一条弧的点为中间点。对于每一条弧(vi,vj),对应有一个对应有一个c(vi,vj)0,(cij)称为弧称为弧的容量。这样的有向图称为容量网络。记为的容量。这样的有向图称为容量网络。记为D=(V,E,C)。1、网络流、网络流义在弧集合义在弧集合E上的一个函数上的一个函数f=f(vi,vj)，称，称f(vi,vj)为弧为弧(vi,vj)上的流量，简记上的流量，简记fij。2、可行流、可行流3、最大流、最大流4、增广链、增广链5、最小截集、最小截集2、可行流与最大流、可行流与最大流定义定义2 满足下列条件的流称为满足下列条件的流称为可行流可行流：1)0 fij cij2)平衡条件：平衡条件：中间点中间点 fij=fji(vi,vj)A(vj,vi)A发点发点vs fsj fjs=v(f)(vs,vj)A(vj,vs)A ftj fjt=v(f)(vt,vj)A收点收点vt，(vj,vt)A式中式中v(f)称为这个可行流的流量，即发点的净输出量称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。（或收点的净输入量）。最大流问题：求一流最大流问题：求一流fij满足满足0 fij cij v(f)i=s fij fji=0 i s，t v(f)i=t且使且使v(f)达到最大。达到最大。3、增广链、增广链 给定可行流给定可行流f=fij，使，使fij=cij的弧称为的弧称为饱和弧饱和弧，使，使fij0的弧称为的弧称为非零流弧非零流弧。若若 是网络中连接发点是网络中连接发点vs和收点和收点vt的一条链，定的一条链，定义链的方向是从义链的方向是从vs到到vt，则链上的弧被分成两类：，则链上的弧被分成两类：前向弧：弧的方向与链的方向一致前向弧：弧的方向与链的方向一致 全体全体+后向弧：弧的方向与链的方向相反后向弧：弧的方向与链的方向相反 全体全体 定义定义3 设设f是一可行流，是一可行流，是从是从vs到到vt的一条链，的一条链，若若 满足下列条件，则称之为（关于流满足下列条件，则称之为（关于流f的）一条的）一条增广链：增广链：在弧在弧(vi,vj)+上，上，0 fijcij 在弧在弧(vi,vj)上，上，0fij cij 4、截集与截量、截集与截量 定义定义4 给定网络给定网络D=(V,A,C)，若点集，若点集V被剖被剖分为两个非空集合分为两个非空集合V1和和V1，使，使vs V1，vt V1，则把弧集，则把弧集(V1,V1)称为是（分离称为是（分离vs和和vt的）的）截集。截集。截集是从截集是从vs到到vt的必经之路。的必经之路。定义定义5 给定一截集给定一截集(V1,V1)，把截集，把截集(V1,V1)中所有弧的容量之和称为这个截集的容量中所有弧的容量之和称为这个截集的容量(截量截量),记为记为C(V1,V1)。v(f)C(V1,V1)图与网络模型Graph Theory网络流问题网络流问题1、流量、流量截量定理截量定理容量网络上任何一个可行流的流量不超过任何一个截集的容量网络上任何一个可行流的流量不超过任何一个截集的截量。截量。2、增广链调整定理、增广链调整定理在增广链上对可行流进行调整可以得到一个流量更大的可在增广链上对可行流进行调整可以得到一个流量更大的可行流。行流。3、最大流定理、最大流定理可行流是最大流的充分必要条件是不存在关于该可行流的可行流是最大流的充分必要条件是不存在关于该可行流的增广链。增广链。步骤步骤：2、标号过程标号过程1、选取一个可行流（可选择零流弧）、选取一个可行流（可选择零流弧）从从Vs出发，出发，在在前向前向弧弧上上(vi,vj)，若，若fij0，则给，则给vj标号标号(Vi,l(vj)，其中其中l(vj)=minl(vi)，fji。二、寻找最大流的标号法二、寻找最大流的标号法(Ford Fulkerson)思想：从一可行流出发，检查关于此流是否思想：从一可行流出发，检查关于此流是否存在增广链。若存在增广链，则增大流存在增广链。若存在增广链，则增大流量，使此量，使此链变为非增广链；这时再检查是非还有增广链，链变为非增广链；这时再检查是非还有增广链，若还有，继续调整，直至不存在增广链为止。若还有，继续调整，直至不存在增广链为止。3、若标号延续到、若标号延续到vt，表明得到一条从，表明得到一条从vs到到vt的增的增广链广链，转入调整阶段，转入调整阶段4，否则当前流即为最大流。，否则当前流即为最大流。4、调整过程、调整过程令调整量为令调整量为=l(vt)令令 fij+(vi,vj)+fij=fij (vi,vj)fij (vi,vj)去掉所有的标号，对新的可行流去掉所有的标号，对新的可行流f=fij，重新进入，重新进入标号过程。标号过程。可结合下图理解其实际涵义。可结合下图理解其实际涵义。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例例 求下列网络的最大流与最小截集。求下列网络的最大流与最小截集。解解一、标号过程一、标号过程则则v1的标号为的标号为(vs,l(v1)，其中，其中l(v1)=minl(vs)，cs1fs1=min+，9 2=2（3）检查）检查v1,在弧在弧(v1,v4)上上,f14=7,c14=9,f140，则则v3的标号为的标号为(-v4,l(v3)，其中，其中l(v3)=minl(v4)，f34=min2，1=1（5）检查）检查v3,在弧在弧(v3,vt)上上,f3t=3,c3t=6,f3tc3t,则则vt的标号为的标号为(v3,l(vt)，其中，其中l(vt)=minl(v3)，c3tf3t=min1，6-3=1这样，我们得到了一增广链这样，我们得到了一增广链,如图所示。如图所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0,)(vs,2)(v1,2)(-v4,1)(v3,1)其中其中+=(vs,v1),(v1,v4),(v3,vt)，=(v3,v4)二、调整过程二、调整过程取调整量为取调整量为=1，在，在 上调整上调整f。在在+上：上：fs1+=7+1=8 f14+=2+1=3 f4t+=5+1=6在在 上：上：f43=11=0s1vtvv3(9,8)(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7)在上图中重复上述标号过程，依次给在上图中重复上述标号过程，依次给vs,v2,v1,v4标号标号后，由于标号无法继续下去，算法结束。这时的流为最后，由于标号无法继续下去，算法结束。这时的流为最大流，最大流的流量为大流，最大流的流量为vvv(4,4)v(f)=8+3=11 与此同时，可找到最小截集与此同时，可找到最小截集(V1,V1)，其中，其中V1为标号点集为标号点集合，合，V1为未标号点集合，弧集合为未标号点集合，弧集合(V1,V1)即为最小截集。即为最小截集。此例中，此例中，V1=vs,v2,v1,v4,V1=v3,vt,(V1,V1)=(v1,v3)，(v4,vt)图与网络模型Graph Theory网络流问题网络流问题容量网络容量网络 N 上最大流的标号（上最大流的标号（Ford-Fulkerson）算法：）算法：下面，我们采用此算法来求解前面的旅行总社计下面，我们采用此算法来求解前面的旅行总社计划问题案例划问题案例图与网络模型Graph Theory最大流问题最大流问题各办事处已订购机票情况表各办事处已订购机票情况表成都成都vs重庆重庆v1武汉武汉v2上海上海v3西安西安v4郑州郑州v5沈阳沈阳v6昆明昆明v7广州广州v8北京北京vt成都成都 重庆重庆 武汉武汉 上海上海 西安西安 郑州郑州 沈阳沈阳 昆明昆明 广州广州 北京北京10 15 12 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10 8 2 6 10 图与网络模型Graph Theory最大流问题最大流问题发点发点vs=成都，收点成都，收点vt=北京。前面已订购机票情况表中的数字即是各北京。前面已订购机票情况表中的数字即是各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零时略去不写，以零流作为初始可行流。时略去不写，以零流作为初始可行流。重重武武昆昆上上广广西西郑郑沈沈京京成成0，+标号，但未检查标号，但未检查标号，但且已检查标号，但且已检查 vs，300+30图与网络模型Graph Theory最大流问题最大流问题重重武武昆昆上上广广西西郑郑沈沈京京成成300，+vs，10vs，15vs，12vs，10vs，8vs，150，+v7，10v7，8vs，120+100+10图与网络模型Graph Theory最大流问题最大流问题重重武武昆昆上上广广西西郑郑沈沈京京成成301066122841221061010000010801801000，+vs，8vs，13v2，4vs，13-v2，4 v1，4-v2，40+44-42+4v1，4图与网络模型Graph Theory最大流问题最大流问题重重武武昆昆上上广广西西郑郑沈沈京京成成30106612280126106101000001080184100vs，8vs，9v2，40，+-v4，6vs，8 v1，6-v4，64+66-60+6vs，9图与网络模型Graph Theory最大流问题最大流问题重重武武昆昆上上广广西西郑郑沈沈京京成成301006122801261061010600010801810100vs，90，+vs，2v2，4vs，9v3，4v2，4v5，4-v5，2v3，4-v5，2v5，4vs，2图与网络模型Graph Theory最大流问题最大流问题重重武武昆昆上上广广西西郑郑沈沈京京成成301006122801261061010600010801810100v(f*)=10+6+12+30+12+10+6=86图与网络模型Graph Theory最小费用大流问题最小费用大流问题五、五、最小费用大流问题最小费用大流问题 前面讨论的旅行社的计划问题中，旅行社解决了将尽可能多的前面讨论的旅行社的计划问题中，旅行社解决了将尽可能多的游客（游客（86人）送往了目的地人）送往了目的地北京，但旅行社计划时没有考虑机票北京，但旅行社计划时没有考虑机票的成本。现在旅行社考虑的问题是既要送出尽可能多的游客（的成本。现在旅行社考虑的问题是既要送出尽可能多的游客（86人），人），又要使机票的总成本最低，应该如何制定新的计划呢？这就是又要使机票的总成本最低，应该如何制定新的计划呢？这就是最小费最小费用大流用大流所研究解决的一类流量问题。所研究解决的一类流量问题。最小费用大流问题还广泛应用于诸如最小费用大流问题还广泛应用于诸如最优匹配最优匹配，运输问题运输问题等一类问等一类问题。题。应该注意的是：最小费用大流问题首先要解决网络上的最大流，目应该注意的是：最小费用大流问题首先要解决网络上的最大流，目的是寻找使总费用达到最小的那个最大流。的是寻找使总费用达到最小的那个最大流。