图论与网络规划ppt课件.ppt

第十章 图论与网络优化,1 图的基本概念,2 最小树问题,3 最短路问题,4 网络最大流问题,5 最小费用最大流问题,一 些 问 题,图论中著名问题. 1736年，图论的创始人Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文.,例：七桥问题,问题：一个散步者能否走过七座桥，且每座桥只走 过一次，最后回到出发点。,例：四色猜想,能否用四种颜色给地图染色，使相邻的国家有不同的颜色。,点：国家；边：两个国家有公共边界。,问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。,公元1852年，格里斯发现无论多么复杂的地图，只要用四种颜色就能将相邻的区域区分开来，这就是所谓“四色猜想”。直到公元1976年，才由美国数学家同时操作三台超大型汁算机作了近200亿个逻辑判断，花费1200个机时，才取得了“四色猜想”的证明。,例：Hamilton图,游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。,公元1859年，哈密尔顿(Hamilton)在给朋友格拉伍斯（Grares）的信中提出了这个游戏。问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。,例：中国邮路问题,一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。,点：路口；边：两路口之间道路，第i条道路长ei。,1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最 短。,例：有甲、乙、丙、丁、戊五个球队，各队之间比赛 情况如表：,点：研究对象（陆地、路口、国家、球队）；,点间连线：对象之间的特定关系（陆地间有桥、路 口之间道路、两国边界、两球队比赛及 结果)。,对称关系：桥、道路、边界；,用不带箭头的连线表示，称为边。,非对称关系：甲队胜乙队，用带箭头的连线表示， 称为弧。,图：点及边（或弧）组成。,实际生活中，人们经常用“图”来表示一些对象以及这些对象之间的特定关系。,如公路或铁路交通图、管网图、通讯联络图等。,对所要研究的问题确定具体对象及这些对象间的性质关系，并用图的形式表示出来，这就是对所研究原问题建立的模型。图是反映对象之间关系的一种工具。,这里所研究的图与平面几何中的图不同。这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。是组合意义下的图。图的理论和方法，就是从形形色色的具体的图以及与它们相关的实际问题中，抽象出共同性的东西，找出其规律、性质、方法，再应用到解决实际问题中去。,图论(Graph Theory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。随着电子计算机的蓬勃发展，图论不仅得到了迅速发展，而且应用非常广泛。它直观清晰，使用方便，易于掌握。应用领域：物理学、化学、控制论、信息论、管理科学、通信系统、交通运输系统、建筑、计算机科学、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。网络规划是图论与线性规划的交叉学科,具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等.,10.1 图的基本概念,一个图(Graph) 定义为三元有序组G=(V(G), E(G), G )，V(G)是图的顶点集合，E(G)是图的边集合，G称为顶点与边之间的关联函数。 V(G)中的元素 vi 称为顶点,E(G)中的元素 ek 称为边.一个图习惯记作 G=(V, E).,当V, E为有限集合时，G称为有限图，否则，称为无限图.,我们只讨论有限图.,一、基本概念,.图,设G是一个图，G=(V(G),E(G)，,则称e 连接u和v，称u和v是e的端点.,若,称端点u，v与边e是关联的，称两个顶点u，v是邻接（相邻）的.两条边e, e1有公共端点v，则称e, e1相邻.,一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的许多性质.,设G是一个图，,G的几何实现,其中：,例,说明,一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身. 并称图形的点为顶点,图形的线为边.图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。,在一个图的几何实现中，两条边的交点可能不是图的顶点。例如,有时也用 m(G)=|E| 表示图 G 中的边数，用 n(G)=|V| 表示图 G 中的顶点个数，简记为m, n.,图 G 中的点数记为 p(G)，边数记为q(G) .在不引起混淆的情况下，简记为 p, q.此时，图 G 可以表示为G = ( p, q ).,平面图,一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图：,非平面图,环、多重边,端点重合为一点的边称为环。连接同一对顶点的多条边称为多重边。,简单图,一个图称为简单图,如果它既没有环也没有多重边.含有多重边的图称为多重图.我们只讨论有限简单图，即顶点集与边集都是有限的图。,只有一个顶点的图称为平凡图；,边集是空集的图称为空图。,完全图K n,完全图是每一对不同顶点都恰有一边的简单图；具有 n 个顶点的完全图记为K n.,二分图（X, Y; E）,二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另一个端点在Y; (X,Y)也称为图的二分划。,完全二分图,K3,3,完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连。完全二分图记为Km,n,X:,Y:,特殊图例,都是极小的非平面图.,K5,K3,3,2.顶点的度（次）,称度为奇数的顶点为奇点；,称度为偶数的顶点为偶点.,设G是一个图，G=(V(G), E(G), G)，定义图G的顶点 v 的度为与顶点v相关联的边数，记作d(v).,定理设G是一个图，则,推论：图中奇点的数目为偶数。,度为1的点称为悬挂点,连结悬挂点的边称为悬挂边.度为0的点称为孤立点。,3.子图,有两个图G和H，如果,称图H是图G的子图，记为,若,且,称H是G的真子图。,称H是G的支撑子图（或生成子图）.,如果 ，,e1,e3,e2,G,v3,v4,v5,v2,v1,H1: 真子图,v3,v5,v2,v1,H2:支撑子图,e1,e3,e2,v3,v4,v5,v2,v1,顶点导出子图,设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为GW。导出子图GV- W记为G-W，即,它是从G中删除W中顶点以及与这些顶点相关联的边所得到的子图。,e1,e3,e2,G,v3,v4,v5,v2,v1,e3,e2,v3,v4,v2,Gv2 ,v3 ,v4 ,G-v1 ,v5 ,边导出子图,设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为GF。记 G-F 表示以 E(G)F 为边集的G的支撑子图，它是从G中删除F 中的边所得到的子图。,如F= e ，则记,e1,e3,e2,G,v3,v4,v5,v2,v1,Ge1 ,e2 ,e3 ,G - e1,e1,e3,e2,v3,v4,v2,v1,4.图的并与交,设G1与G2都是图G的子图；若 ，则称G1与G2不相交；若 ，则称G1与G2边不重的。定义图G1与G2的和，记为，是G的一个子图，其顶点集为 ,边集为 若G1与G2是不相交的，则记。类似的可以定义G1与G2的交 ，此时要求,同构,给定两个图,如果存在两个一一对应的关系,使的,称G和H是同构的，记为,同构图例,G,H,e6,e4,e2,e1,e3,e5,f1,f2,f6,f3,f5,f4,v1,v2,v3,v4,u1,u2,u3,u4,径,顶点vk叫W的终点，顶点v0 称为W的起点， 顶点vi 叫W的内部顶点(内点)， 整数k称为W的长度。 在简单图中，径可由顶点序列表示。,图G的一个有限的点边交错序列称为从v0到vk的径；,其中vi 与vi+1是边ei的顶点;,5. 连通性,链、路,如果径W 的边各不相同，则称W为一条链，,如果W 顶点互不相同，则称W 是一条路。,链长是W 中边的个数 k.,记路长,链：w c x d y h w b v g y路：x c w h y e u a v,圈(回路),如果径 W 的起点和终点相同且有正长度，则称它是一个闭径；如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。,圈：u a v b w h y e u,a,b,d,e,f,g,h,c,u,v,y,x,w,定理：一个图是二分图当且仅当图中不存在奇圈.,连通性,图G称为连通的，如果G的任意两个顶点u 和 v 中存在一条(u,v)路。,不连通图（分离图）至少有两个连通分支。,用w 表示G的连通分支数。,一个连通图称为一个连通分支。,割集：删除掉连通图中的若干条必要的边后，使得图不连通，则这些边的集合称为图的一个割集.,割边：删除掉这条边后图G不连通。,割点：删除掉这个点后图G不连通。,Euler圈,Euler圈是指过所有边一次且恰好一次的闭链。Euler链是指过所有边一次且恰好一次的链。,Euler链：y d x c w h y e u a v f y g v b w,Euler圈：所有的顶点度数为偶数。Euler链：除了两个顶点度数为奇数,其余为偶数.,Euler 型（Euler 图）,定理设G是连通图，则G是Euler 型的充要条件是G没有奇次数的顶点。推论设G是一个连通图，则G有Euler 链当且仅当G最多有两个奇数次数的顶点。,如果图G包含一条Euler圈，则称G是Euler型的.,Hamilton 型（Hamilton 图）,Hamilton路是指包含G的每个顶点的一条路。Hamilton圈是指包含G的每个顶点的一个圈。,如果图G包含一条Hamilton圈，则称G是Hamilton型的.,6. 赋权图,对图G的每条边e，赋予一实数w(e),称为边e的权，可得一赋权图（网络）。定义赋权图 G 的权为 G 的所有边权的总和。赋权图中一条路的权称为路长。,7. 有向图,图G的每条边如果有方向，称为有向图。有向图的边称为有向弧（简称弧）,用ai 表示.有向图的各弧用边对应替换后所得的无向图称为该有向图的基础图。度：出度、入度相应的可以定义有向图的路、圈、连通性、有向网络等。,1. 邻接矩阵,设G是一个图，G=(V(G),E(G),G)，定义图G的邻接矩阵A(G) =(aij)为 nn 矩阵, 其中aij为连接vi与vj的边数。,二、图的矩阵表示,2. 关联矩阵,取值可能为0、1、2。,设G是一个图，G=(V(G),E(G),G)，定义图G 的关联矩阵M(G) =(mij)为nm矩阵, 其中mij为vi与ej的关联次数。,注,关联矩阵和邻接矩阵统称图的矩阵表示。,图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮于计算机中。,例,2,2,2,2,2,2,2,4+3+3+4=14=27,关联矩阵性质,图G的关联矩阵M=(mij)为mn矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于2.,因此，图G的关联矩阵M所有元素之和既等于所有顶点的度之和，又等于边数的2倍。,10.2 树,一、树的概念和性质二、图的支撑树三、最小支撑树,一、树的概念和性质,树是图论中结构最简单但又十分重要的图。,例 某企业的组织结构可用下图表示.,树（tree）是一个不包含圈的简单连通图。树中度为1的点称为树叶，度大于1的点称为分枝点.具有k个连通分支的不包含圈的图称为k-树，或森林.下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。,树的性质,设G是一个简单图， ,则下列六个命题是等价的.G是一棵树。G无圈且 m = n-1。G连通且 m = n-1。G连通并且每条边都是割边。G中任意两点都有唯一的路相连。G无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。,二、图的支撑树（生成树）,若图G的支撑子图是一棵树，则称该树为图G的支撑树（生成树）。或简称为图G的树.支撑树也称为连通图的极小连通支撑子图。图G有支撑树的充要条件为G是连通图.很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。,图的支撑树的求法,寻找图的支撑树的方法有两种：破圈法、避圈法.,破圈法：在图G中任意取一个圈，从圈上任意去掉一条边，将这个圈破掉。重复这个步骤直到不含圈为止，所得图即为支撑树。,v1,v2,v4,v5,v3,避圈法：在给定的图G中，每步选出一条边，使它与已选边不构成圈，直到选够n-1条边为止。,按照边的选法不同,可分为两种：深探法,广探法.,深探法:,避圈法：在给定的图G中，每步选出一条边，使它与已选边不构成圈，直到选够n-1条边为止。,按照边的选法不同,可分为两种：深探法,广探法.,广探法:,设G是一个赋权图，T为G的一个支撑树。定义T的权为：G中权最小的支撑树称为G的最小支撑树(最小树).,三、最小支撑树问题,许多网络问题都可以归结为最小树问题。例如:设计长度最小的公路网把若干城市联系起来;设计用料最省的电话线网把有关单位联系起来等.,下面介绍求最小树的两种算法.,Step0 把边按权的大小从小到大排列得： 置 Step1 若 ，则停，此时GS即为所 求的最小树；否则，转向Step2。Step2 如果 GS+e j不构成回路，则令 转向Step1；否则，令j=j+1转向Step2。,算法1：Kruskal算法（类似于广探法）（1965）,思想:开始选一条权最小的边,以后每一步,总从未选的边中选一条权最小的边,使它与已选边不构成圈.,算例1：,利用Kruskal算法求最小树。,评注,Kruskal算法的总计算量为 ，有效性不太好。求最小树的一个好的算法是Dijkstra于1959年提出的，算法的实质是在图的 个独立割集中，取每个割集的一条极小边来构成最小树。,算法2：Dijkstra算法（类似于深探法）,Step0 置Step1 取 置 Step2 若 ，则停止；否则，置 ，返回Step1.,算例2：,利用Dijkstra算法求最小树。,算法3：破圈法,破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。Step1 若G不含圈，则停止；否则在G中找一个 圈C，取圈C中权值最大的一条边e .Step2 置 G = G - e ，返回Step1。,算例3：,利用破圈法求最小树。,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,最小连接问题,作为最小树的应用问题之一是所谓的连接问题：欲建造一个连接若干城镇（矿区或工业区）的铁路网，给定城镇i和j之间直通线路的造价为 cij ，试设计一个总造价最小的铁路运输图。把每个城镇看作是具有权cij的赋权图G的一个顶点。显然连接问题可以表述成：在赋权图G中，求出具有最小权的支撑树。,10.3 最短路问题,最短路问题是网络理论中应用最广泛的问题之一.许多优化问题可以使用这个模型如设备更新、管道铺设、线路安排、厂区布局等.我们曾介绍了最短路问题的动态规划解法，但某些最短路问题(如道路不能整齐分段者)构造动态规划方程比较困准、而图论方法则比较有效。,最短路问题：在一个赋权图G上，给定两个顶点u和 v，在所有连接顶点u和 v 的路中，寻找路长最短的路（称为u和 v最短路.） u和 v最短路的路长也称为u和 v的距离-d(u,v).,有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、或求网络中任意两点间的最短路.,一、网络无负权的最短路,本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。算法的基本思路基于以下原理：若序列vs ,v1 ,vn是从vs到vn的最短路，则序列vs ,v1 ,vn-1必为从vs到vn-1的最短路。,Dijkstra算法,Dijkstra算法基本思想,Dijkstra算法的基本思想是从vs出发，逐步地向外探寻最短路，采用标号法。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路长（称为P标号），或者是从vs到该点的最短路长的上界（称为T标号）。算法每一步都把某个顶点的T 标号改为P 标号， 当终点vt 得到 P 标号时，计算结束。最多n-1步。,计算实例：,求连接 vs、vt 的最短路.,开始，给vs以 P 标号，P(vs)=0,其余各点给 T 标号 T(vi)=+.,Step 1:,迭代 1,Dijkstra算法基本步骤：,若 vi 为刚得到 P 标号的点,考虑这样的点 vj : (vi ,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,2,4,5,迭代 1,考察vs ,T(v2)=minT(v2),P(vs)+ws2= min+,0+5=5,T(v1)=minT(v1),P(vs)+ws1= min+,0+2=2,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,2,4,5,-,2,迭代 1,全部T标号中,T(v1)最小,令P(v1)=2,记录路径(vs ,v1).,9,4,若 vi 为刚得到 P 标号的点,考虑这样的点 vj : (vi ,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,迭代 2,考察v1 ,T(v4)=minT(v4),P(v1)+w14= min+,2+7=9,T(v2)=minT(v2),P(v1)+w12= min5,2+2=4,4,4,迭代 2,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,-,-,全部 T 标号中,T(v2),T(v3)最小,令P(v2)=4, P(v3)=4,记录路径(v1 ,v2), (v1 ,v4),.,7,迭代 3,若 vi 为刚得到 P 标号的点,考虑这样的点 vj : (vi ,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,7,迭代 3,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,-,迭代 4,若 vi 为刚得到 P 标号的点,考虑这样的点 vj : (vi ,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,8,14,迭代 4,8,-,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,迭代 5,13,若 vi 为刚得到 P 标号的点,考虑这样的点 vj : (vi ,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,迭代 5,13,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,-,最短路,Dijkstra算法不仅找到了所求最短路，而且找到了从 vs 点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。,开始，给vs以 P 标号，P(vs)=0,其余各点给 T 标号 T(vi)=+.,Step 1:,若 vi 为刚得到 P 标号的点,考虑这样的点 vj : (vi ,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,Dijkstra算法步骤：,(2) 考察vs ,T(v2)=minT(v2),P(vs)+ws2= min+,0+5=5,T(v1)=minT(v1),P(vs)+ws1= min+,0+2=2,(3) 全部T标号中,T(v1)最小,令P(v1)=2,记录路径(vs ,v1).,(4)考察v1 ,T(v4)=minT(v4),P(v1)+w14= min+,2+7=9,T(v2)=minT(v2),P(v1)+w12= min5,2+2=4,(5) 全部 T 标号中,T(v2),T(v3)最小,令P(v2)=4, P(v3)=4, 记录路径(v1 ,v2), (v1 ,v4),.,T(v3)=minT(v3),P(vs)+ws3= min+,0+4=4,解: (1)首先，给vs以 P 标号，P(vs)=0,其余各点给 T 标号 T(vi)=+.,.,Ford算法基本思想：为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路，逐次放宽条件。即第一次逼近是找v0到vn的最短路，但限于最短路只允许有一条边（弧），其距离记为d1(v0 ,vn).简记为d 1(vn).第二次逼近，再找v0到vn的最短路，其限制条件放宽到允许最短路不超过两条边（弧），其距离记为d 2(vn).到第m次逼近,d m(vn)表示由v0到vn的不超过m条边（弧）组成的最短路的距离。最多p-1次.,二、网络有负权的最短路,Ford算法,Ford算法基本步骤：,(1) 令m=1,令d1(v0)=0, d1(vi)=w(v0 ,vi).,解： d1(v0)=0, d1(v1)=2, d1(v2)=1, d1(v3)=-2.,0,2,1,-2,第一次逼近,(2) 令,解： d2(v1)=min d1(v1)+w(v1,v1), d1(v2)+w(v2,v1), d1(v3)+w(v3,v1) ,0,2,1,-2,当vi , v 为同一个点时，有w(v ,vi)=0.,=min 2+0,1+, -2+3 =1.,1,d2(v2)=min d1(v1)+w(v1,v2), d1(v2)+w(v2,v2), d1(v3)+w(v3,v2) ,=min 2-2,1+0, -2+ =0.,0,d2(v3)=min d1(v1)+w(v1,v3), d1(v2)+w(v2,v3), d1(v3)+w(v3,v3) ,=min 2+,1+1, -2+0 =-2.,第二次逼近,(3)若m+1=p 则停止。否则m=m+1,转(2).,解： d3(v1)=min d2(v1)+w(v1,v1), d2(v2)+w(v2,v1), d2(v3)+w(v3,v1) ,0,1,0,-2,=min 1+0,0+, -2+3 =1.,d3(v2)=min d2(v1)+w(v1,v2), d2(v2)+w(v2,v2), d2(v3)+w(v3,v2) ,=min 1-2,0+0, -2+ =-1.,-1,d3(v3)=min d2(v1)+w(v1,v3), d2(v2)+w(v2,v3), d2(v3)+w(v3,v3) ,=min 1+,0+1, -2+0 =-2.,第三次逼近,(2) 令,当vi , v 为同一个点时，有w(v ,vi)=0.,(3)若m+1=p 则停止。否则m=m+1,转(2).,最后解得：d3(v1)=1， d3(v2)= -1， d3(v3)= -2.,0,1,-1,-2,即v0到v1最短路长度为 d3(v1)=1，最短路为v0,v3,v1 .,即v0到v2最短路长度为 d3(v2)= -1,最短路为v0,v3,v1,v2 .,即v0到v3最短路长度为 d3(v3)= -2,最短路为v0,v3 .,Ford算法基本步骤：,(1) 令m=1,令d1(v0)=0, d1(vi)=w(v0 ,vi).,(2) 令,当vi , v 为同一个点时，有w(v ,vi)=0.,(3)若m+1=p 则停止。否则m=m+1,转(2).,某些问题中，要求网络上任意两点间的最短路。这类问题可以用 Dijkstra 算法依次改变起点的办法计算，但比较繁琐。而 F1oyd 方法(1962年)可直接求出网络中任意两点间的最短路。,令网络的权矩阵为,三、Floyd算法,其中,权矩阵：,图中有四条无向边，每条均可化为两条方向相反的有向边。,则得权矩阵为：,(1) 输入权矩阵 D(0)=D;(2) 计算 其中(3) 中元素,Floyd算法基本步骤：,就是vi到vj的,最短路长.,计算实例：求图中任意两点间的最短路。,解: (1)输入权矩阵 D(0)=D.,(2) 计算 其中,计算,如：,其中,0,5,1,2,5,0,6,7,2,2 3 0 2 8,2 7 3 0 4, 2 4 4 0,其中,表示从vi点到vj点,或直接有边或借v1点为中间点时的最短路长。,其中,表示从vi点到vj点,最多经中间点v1 , v2的最短路长。,(2) 计算 其中,计算,其中,表示从vi点到vj点,最多经中间点v1 , v2 , v3的最短路长。,(2) 计算 其中,计算,其中,表示从vi点到vj点最多经中间点v1,v2,v3,v4,v5,计算,的所有路中的最短路长。,所以D(5)就给出了任意两点间不论几步到达的最短路长。,如果还希望给出具体的最短路经，则在运算过程中要保留下标信息，即 等等。,如在D(1)中的 是由,得到的，所以 可以写成 .,而D(2)中的 是由,得到的，所以 可以写成 .,而D(2)中的 是由,得到的，所以 可以写成 .,而D(3)中的 是由,得到的，而 所以 可以写成 等.,由此,应 用 举 例,例1 设备更新问题.,某工厂使用一台设备，每年年初工厂都要作出决定如果继续使用旧的，要付维路费；若购买一台新设备要付购买费。试制定一个5年的更新计划，使总支出最少。,若已知设备在各年年初的价格为：,还知使用不同年数的设备所需要的维修费用为：,可供选则的设备更新方案是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为 5，五年合计为 25，于是五年总的支付费用为 59+25=84.,又如，决定在第一、三、五年各购进一台新设备，则其购置费用为11+12+13=36，维修费用为 5+6+5+6+5=27，于是五年总的支付费用为 36+27=63.,可把这个问题化为最短路问题。,用点vi表示第i年年初购进一台新设备虚设一个点v6 ,表示第五年年底。弧(vi ,vj)表示第i年初购进的设备一直使用到第j年年初(即第j-1年年底).,弧(vi ,vj)上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买、维修的全部费用.例如 (v1 ,v4): 购置费11，维修费5+6+8=19，总计30.,这样设备更新问题就变为：求从v到v6 的最短路。求解得： v1 , v3 , v6 及 v1 , v4 , v6 均为最短路。总的支付费用均为53。,已知某地区的交通网络如图所示，其中点代表居民小区，便表示公路，wij为小区间公路距离问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近?,例2 选址问题.,解 ：实际要求出图的中心，可以化为一系列求最短路问题。先求出v1到其它各点的最短路长dj ,令D(v1)max(d1, d2 , , d7)表示若医院建在v1，则离医院最远的小区距离为D(v1) 。再依次计算v2 , v3 , , v7 到其余各点的最短路，类似求出D(v2),D(v3) , , D(v7) 。D(vi)中最小者即为所求，计算结果见下表。,由于D(v6)48 最小，所以医院应建在v6，此时离医院最远的小区(v5) 距离为48 .,不同网络中流的意义不同，流本身是一种输送，可以把它们统称为运输网络的流。,许多系统包含了流量问题。例如在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流，等等.,10.4 最大流问题,管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量，上述问题就是要讨论如何充分利用装置的能力以取得最好效果(流量最大)，这类问题通常称为最大流问题。,50年代福持(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。,一、最大流基本概念,1. 网络与流,给一个有向连通图D=(V,A)，在V 中指定了一个点，称为发点(或源，记为vs，其入度为0)，和另一个点，称为收点(或汇，记为vt，其出度为0)，其余点叫中间点， 对D的每条弧(vi ,vj)对应有一个非负数cij ,称为弧的容量，这样的网络D称为容量网络，常记做D =(V,A,C)。对任一D中的弧(vi ,vj)有流量fij ，称集合 f= fij 为网络D上的一个流。,例 网络 D 及其一个流,vs为发点(源)，vt为收点(汇)，其余点为中间点。对每条弧(vi ,vj)，有弧的容量cij ，弧的流量fij ，常记做(fij , cij ).,如 fs1 = 5， f12 = 4 ， f42 = 2.,集合 f= fij 称为网络D上的一个流.,2. 可行流与最大流,称满足下列条件的流 f 为可行流：(1)容量限制条件：对所有弧(vi ,vj) ，成立(2)平衡条件：对所有中间顶点 v ，成立其中，f +(v)是流出v 的总流量， f -(v)是流入v的总流量，对于源点v s和汇点 vt ，流出源点vs 的流量等于流入汇点v t的流量.,称之为流 f 的值，记为val f 或v( f ).,可行流总是存在的。例如令所有弧的流量 fij=0，就得到一个可行流 f = 0 (称为零流)，其流量 v(f)=0.所谓最大流问题就是在容量网络中，寻找流量最大的可行流。,最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。,v(f)=7.,3. 增广链,一个可行流 f = fij ，称 fij= cij 的弧为饱和弧，称 fij 0的弧为非零流弧.,饱和弧,设P是网络D的一条连接源点vs 和汇点vt 的链，定义链P的方向是从vs 到vt ，前向弧弧的方向与P的方向一致；全体记为P +.后向弧弧的方向与P的方向相反；全体记为P -.,链P ：,注：链不是有向路，链的每一边去掉方向是一条路.,则P中的弧可分为两类：,f 是一个可行流，P是从vs 到vt 的一条链， 如果(1) P 的每一前向弧都是不饱和弧（ ）;(2) P 的每一后向弧都是非零流弧（ ）；则称 P 是网络 D 的关于可行流 f 的一条增广链。简称增广链。,增广链 P ：,4. 割集,设S、S是网络D的两个顶点子集,且且 , 定义D的一个割集(简称割)为也称为分离vs和vt一个割集，可简记为K .,割集,网络的割集有多个，其中割集容量最小者称为网络的最小割集容量(简称最小割)。,显然，对于网络的任意一个可行流 f 和割(S,S)，成立,因此,若能找到一个可行流 f ，一个割集(S,S)，使得成立则 f 必是最大流，而(S,S)是最小割。,定理：设f 是网络D上的一个可行流，则 f 是一个最大流当且仅当网络D不存在 f 的增广链。,增广链 P ：,最大流最小割定理：任一个网络D中，从vs到vt 的最大流的流量等于分离vs和vt 的最小割的容量.,定理：设f 是网络D上的一个可行流，则 f 是一个最大流当且仅当网络D不存在f 的增广链。证明(必要性) 设f 是一个最大流，假如D中存在f 的增广链P,则可以得到一个流值更大的流 f 1,使得,构造过程如下：,其中,证明(充分性)设网络D不存在f 的增广链，令S表示D中可通过用不饱和路把源点与之相连的所有顶点集合，Sc表示S的余集。则从而K=(S, Sc)是D的割集，进而可得K=(S, Sc)中的弧都是饱和弧，而 K1=(Sc, S)中的弧都是0流弧， 否则将产生网络D 的一条增广链。因此，f 的流值等于割集K的割量，所以， f是一个最大流。,二、寻找最大流的标号算法(Ford-Fulkerson算法),Ford -Fulkerson 算法基本思想：从任意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值,进而得到一个新可行流；对新流继续寻找增广链，依次进行下去，直到一个最大流为止.分两步：1 标号过程(寻找增广链)；2 调整过程.每个点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。,Ford 与 Fulkerson 在1957年提出一个求解网络最大流问题的算法，称为Ford -Fulkerson 算法。,Ford -Fulkerson 算法步骤：,1. 标号过程(寻找流 f 的增广链)(1) 给网络赋一个初始0流f 0；给 vs 标号(-,);(2) 选择一个已标号的点 vi , 对于vi 的所有未给标号的邻接点vk , 按下列规则处理： (a) 对每条弧(vi , vk ) ,如果 , 则给 vk 标号 (+ vi , l(vk) ), 其中 (b) 对每条弧(vk , vi ) ,如果 , 则给 vk 标号 (- vi , l(vk) ), 其中(3) 重复(2)直到 vt 被标号或不再有点可标号为止.若vt 得到标号，说明存在一条增广链，转调整过程.若vt 未获得标号,标号无法进行时,说明 f 已是最大流.,Ford -Fulkerson 算法步骤：,2. 调整过程 (1) 令(2) 去掉所有标号，对新可行流 f 1重新进入标号过程.,算例：求下面网络的最大流.,(1) 给网络赋一个初始0流 f 0 ；给 vs 标号(-,);,(-,),(a)对弧(vi , vk) ,若 , 则给 vk 标号(+ vi , l(vk) ), 其中(b) 对弧(vk , vi) ,若 , 则给 vk 标号(- vi , l(vk) ), 其中,标号过程1,(+vs,8),(+vs,2),(+v1,5),(+v3,2),(+v2,5),找到流 f 0 的增广链 P0 = vs v1 v2 vt，,(-,),调整过程1,(+vs,8),(+vs,2),(+v1,5),(+v3,2),(+v2,5),找到流 f 0 的增广链 P0 = vs v1 v2 vt，,2. 调整流量,调整量,=5.,5,5,5,调整流值得流值为5的新可行流 f 1 .,给 vs 标号(-,);,(-,),(a)对弧(vi , vk) ,若 , 则给 vk 标号(+ vi , l(vk) ), 其中(b) 对弧(vk , vi) ,若 , 则给 vk 标号(- vi , l(vk) ), 其中,标号过程2,(+vs,3),(+vs,2),(+v3,2),(+v3,2),(+v2,2),找到流 f 1 的增广链 P1 = vs v3 v2 vt ，,得新可行流 f 1 ，,重新进入标号过程.,(-,),调整过程2,(+vs,3),(+vs,2),(+v3,2),(+v3,2),(+v2,2),找到流 f 1 的增广链 P1 = vs v3 v2 vt ，,2. 调整流量,调整量,=2.,2,调整流值得流值为7的新可行流 f 2 .,2,7,给 vs 标号(-,);,(-,),(a)对弧(vi , vk) ,若 , 则给 vk 标号(+ vi , l(vk) ), 其中(b) 对弧(vk , vi) ,若 , 则给 vk 标号(- vi , l(vk) ), 其中,标号过程3,(+vs,3),(+v1,3),(+v3,3),(+v3,3),(+v4,3),找到流 f 2 的增广链 P2 = vs v1 v3 v4 vt ，,得新可行流 f 2 ，,重新进入标号过程.,(-,),调整过程3,(+vs,3),(+v