运筹学图与网络分析.ppt

第 八 章 图 与 网 络 分 析,图的基本概念 最小树问题 中国邮路问题 网络最短路问题 网络最大流问题,几个图论问题,哥尼斯堡七空桥 中国邮路问题 球队间比赛问题,哥尼斯堡七空桥,哥尼斯堡七座桥问题是200年前数学家欧拉所研究的问题之一。 哥尼斯堡现名加里宁格勒，城中有小岛，周围有七座桥架立在波列格尔河上。 欧拉想：在城中散步时，能否每座桥只走一次，走遍所有的七座桥。,一笔画问题,图1,中国邮路问题 我国数学家管梅谷教授1962年首次提出，并给出了它的解法(奇偶点图上作业法)。 邮递员在送报刊信件时，从邮局出发，一般地每次都要走遍所负责的全部街道，任务完成后返回邮局。那么邮递员应该选择哪一条路线才能以尽可能少的路程走完所有的街道呢？,有A、B、C、D、E五支球队，他们之间的比赛情况可以用图表示出来。已知A队和其他各队都比赛过一次，B队和A、C队比赛过，D队和E、C队比赛过，E队和A、D队比赛过。,图2,图3,如果在比赛中： A胜E， B胜C， A胜D， C胜A， E胜D， A胜B，,注：本章所研究的图与平面几何中的图不 同，这里我们只关心图有几个点，点与点 之间有无连线，两条线有无公共顶点，点 与线是否有关联，至于连线的方式是直线 还是曲线，点与点的相对位置如何都是无 关紧要的。,图4,图的基本概念,若点与点之间的连线没有方向，称为边，由此构成的图为无向图。记为: G=（V，E）其中V是G的点的集合，E为G的边的集合，连接Vi，Vj的边记为Vi，Vj或Vj，Vi,v1,v2,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,e9,e10,图是由点和点与点之间的连线组成。,若点与点之间的连线有方向，称为弧，由此构成的图为有向图。记为: D=（V，A），其中V是G的点的集合，A为G的弧的集合，一条方向为从Vi指向Vj的弧记为(Vi，Vj),v1,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,v2,相邻点：两点之间的边属于E 相邻边：如果两条边有一个公共端点 环：边的两个端点相同 多重边(平行边)：两个点之间有多于一条边(弧) 多重图: 无环但允许有多重边的图 简单图：无环且无多重边的图 注:在有向图中，如果两点之间有不同方向的两条弧，不是多重边,端点的次d(v)：点 v 作为端点的边的个数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1；悬挂边：与悬挂点连接的边， 孤立点：d(v)=0；空图：E = ，无边图。,在有向图中，以Vi为始点的边数称为Vi的出次，以Vi为终点的边数称为Vi的入次，入次和出次的和称为该点的次。 有向图中所有顶点的入次之和等于所有顶点的的出次之和。,图的连通性： 链：由两两相邻的点及其相关联的边构成的点边序列。如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn v0 , vn分别为链的起点和终点 简单链：链中所含的边均不相同。 初等链：链中所含的点均不相同，也称通路。 圈：起点和终点相同的链。,e8,是一条链，且是开链，也是简单链，但不是初等链，因为v1出现两次。,是一个圈。,v3,e1,e2,e3,通路：由两两相邻的点及其相关联的弧构成的点弧交错序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn v0 , vn分别为链的起点和终点 回路：通路的起点和终点相同 连通图：图中任意两点之间均至少有一条链相连，否则称作不连通图。 任何一个不连通的图都可以分为若干个连同子图，每一个都称为原图的一个分图,例如图中，v1和v6之间没有通路，因此它不是连通图， 而如果去掉v6，则构成一个连通图。,连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。,子图 设 G1 = V1 , E1 , G2 = V2 , E2 子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图； 真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图； 部分图：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图；,部分图,子图,必须指出，并不是从图G1中任选一些顶点和边在一起就组成G1的子图G1，而只有在G1中的一条边以及连接该边的两个端点均选入G2时，G2才是G1的子图。,真子图,v1,部分图,若T是图G(V，E)的部分图，且T是树，则称T为G的部分树。 若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，也称为G的一个余树。 余树不一定是树！,一个没有圈的图称为一个无圈图或称为林。 一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。,树与部分树,网络 点和边带有某种数量指标的图称为网络，或称为赋权图。,最小树问题：选取网络中的部分图，使得网络连通，且使总权数最小。 在实际应用中，经常碰到需要求一个赋权连通图的最小树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。 求最小树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为破圈法，一种称为取边避圈法。,网络最小树问题,取边避圈法 方法步骤：依次在图中取一个权值最小的边，或者是相对最短的边，并且在每次取边时都不能与已取的边构成圈。 首先在图中选最短的边，并且将与之关联的两个点标记， 然后每次都在标记点和未标记点间可能的边中取一个最短的边，并将新选的边标记， 重复上述过程，直到所有的点均被标记了。,1,4,3,2,1,6,7,2,2,5,3,破圈法,方法步骤： 在网络图中寻找一个圈，若已经无圈则转步骤3。 在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转步骤1。 若q=p-1(边数=定点数-1)，则已找到最小树，否则网络图不连通，无最小树。,课堂练习： P224 2.a）,问题定义：在一个赋权图上求一个圈，经过图中每一条边至少一次，使圈中各边权值的总和为最小。,中 国 邮 路 问 题,比如圈：v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5,欧拉链与欧拉圈 经过且仅经过图中每一条边一次的链称为欧拉链，经过且仅经过图中每一条边一次的圈称为欧拉圈,定理 连通多重图中含有欧拉链的充分必要条件是图中奇点的个数为0或2。且当且仅当没有奇点时图中含有欧拉圈，即没有奇点的连通图必含有欧拉圈。,E=v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5,对于不含奇点的连通图，中国邮路问题就是要找图中的欧拉圈。,v1,v2,v3,v4,v5,v6,含有奇点的连通图中不含欧拉圈，此时，最优的邮递路线是什么呢？,求解中国邮路问题的奇偶点图上作业法,奇偶点表上作业法 (1)找出奇点(一定为偶数个)，在每两个奇点之间找一条链，在这些链经过的所有边上增加一条边，这样所有的奇点变为偶点，一定存在欧拉圈，但是不一定是路线最短的，所以需要检验和调整。 (2)检验增加的边的权值是否是最小的。 定理3 假设M是使得图G中不含奇点的所有增加边，则M是权值总和为最小的增加边的充分必要条件是： 1)图G中每条边上最多增加一条边； 2)在图G的每个圈上，增加的边的总权值不超过该圈总权值的一半。 如果上述两个条件都满足则已经找到权值最小的欧拉圈 否则转入3) 3)调整增加边。如果1)不满足，则从该条边的增加边中去掉偶数条； 如果2)不满足，则将这个圈上的增加边去掉，将该圈的其余边上添加增 加边，转入(2),v1，v6，v5，v4，v6，v2，v6，v3，v4，v3，v2，v1,不满足定理3条件,网络 对有向图D=(V,A)，如果对于有向图D中的每一条弧(vi,vj) A，都有一个数w(vi,vj) 与它对应，此时称D为一个网络，或称赋权有向图。 有向网络：网络中每个边都是有向边； 无向网络：网络中每个边都是无向边； 混合网络：网络中既有有向边，又有无向边； 网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。,网 络 最 短 路 问 题,一般的最短路问题描述： 给定一个赋权有向图D=(V,A)，对每一个弧a=(vi,vj)，相应地有权w(a)=wij，又给定D中的任何两个顶点vs和vt ，设P是从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P)，最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即一条从vs到vt的路P0使得：,路P0的权称为从vs到vt的距离，记为d(vs,vt)。,有向图权值非负- Dijkstra算法,Dijkstra算法的基本步骤(权值非负) 1.给顶点v1标号(0)，v1称为已标号点，记标号点集为V1=v1 2.在未标号点集V2中找出与标号点集V1中的顶点vi有弧相连(并且以vi为起点)的点vj， 3.在第2步选出的点中，选出满足下面条件的点vk，并给vk标号(l,L1k)，其中l为第一标号， L1k为第二标号,为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk相邻的点是vl,4. 若最后一个顶点vn未标号，则转回第2步；若vn已标号，则从vn开始，按照第一个标号逆向追踪，直到v1，就得到从v1到vn的最短路，vn的第二个标号表示最短路的长度。,求从v1到v8的最短路,(0),(1,1),(1,3),(3,5),(2,6),(5,10),(5,9),(5,12),注：在给顶点编号时，如果在多个为标号点均取得最小值Llk则对这多个点同时标号，这些点的第二个标号相同，但是第一个标号不一定相同。,课堂练习： P225 6. a) 和 b),有向图某些权值为负 1. 先对图中各个点按照Dijkstra算法标号，称之为第一次标号，令m=1，转入第二步； 2. 对图中除了v1以外的所有点进行m+1次标号，记L1k(m+1)为对顶点vk的第m+1次标号的第二个标号值，计算公式如下：,3.如果对所有的点L1k(m)= L1k(m+1)都成立则逆向追踪，找出最短路，算法终止；若存在L1k(m) L1k(m+1), 则令m=m+1，返回第2步,求从v1到v4的最短路,(0),(1,2),(1,3),(2,1),(0),(3,1),(1,3),(2,0),课堂练习: P225 7,无向图,将算法稍作修改：在未标号点集中 找出与标号点vi有边相连的点vj,网络最大流问题,下图表示从产地v1到销地v6的交通网，弧旁边的数字表示这条运输线的最大通过能力，产品经过这个交通网从v1运到v6，要求制定一个运输方案使得从v1运到v6的产品数量最多。,基本概念,网络与流 对有向图D=(V,A)，如果其中指定某一点vs为发点，另一点vt为收点，其他点则称为中间点。若对于有向图D中的每一条弧(vi,vj) A，都有一个数c(vi,vj) 0与它对应，称c为弧的容量，记为D=(V,A ,C) 定义在弧集合A上的一个函数f=f(vi,vj)称为网络D上的流，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij,可行流： 满足下述条件的流称为可行流： (1)容量限制：对于每一个弧(vi,vj) A， 0fij cij (2)平衡条件： 对于中间点：流出量等于流入量，即对于每个i(is,t)有,对于发点：,对于收点：,称v(f)为可行流的流量，发点的净输出量等于收点的净输入量。,最大流问题就是要找出一个可行流使得v(f)达到最大,饱和弧和非饱和弧 网络D=(V,A ,C)，f=f(vi,vj)是D的可行流，则如果某一条弧(vi,vj) A满足 (1) fij = cij ，则称(vi,vj)为饱和弧； (2) fij 0 ， 则称(vi,vj)为非零流弧； 前向弧和后向弧 网络D中与给定的链 方向一致的弧 称为前向弧，记作 ； 与给定的链方向相反的弧称为后向弧，记作 ；,增广链(可扩充链),4,0,0,2,1,大家想想：增广链的意义在哪里？,根据定理，对于给定的可行流f，要判断它是不是最大流只需要判断D中有没有关于f的增广链。 如果有，则需要对f进行改进；如果没有增广链，则已经得到最大流。,定理：可行流f*是最大流，当且仅当不存在关于f*的增广链,寻找最大流的标号法,网络D中的点分为两类，一类是标号点(属于V1* )，一类是非标号点(不属于V1* ) ； 标号点有两类一类是已检查的，一类是未检查的。每个标号点有两个标号：第一个标号表示这个点的标号是从哪一点得到的，以便进一步找出增广链，第二个标号是用来表示方向,2.标号过程,从vi出发的弧,进入vi的弧,1.确定初始可行流,根据图中弧的容量限制，确定一个初始的可行流，可以取零流。,vi变为标号且已检查的点，在vi旁加上*以示区别,3.调整过程,前向弧,后向弧,用标号法求如下图所示的网络最大流 图中已经给出初始流。,(8,5),vs,v2,v1,v4,v3,vt,(2,2),(6,5),(10,4),(7,2),(9,5),(6,0),(3,2),(5,2),(5,3),(8，5),vs,v2,v1,v4,v3,vt,(2,2),(6,5),(1