运筹学_图与网络分析.ppt

1、第 八 章图 与 网 络 分 析,图的基本概念 最小树问题 中国邮路问题 网络最短路问题 网络最大流问题,几个图论问题,哥尼斯堡七空桥 中国邮路问题 球队间比赛问题,哥尼斯堡七空桥,哥尼斯堡七座桥问题是200年前数学家欧拉所研究的问题之一。 哥尼斯堡现名加里宁格勒，城中有小岛，周围有七座桥架立在波列格尔河上。 欧拉想：在城中散步时，能否每座桥只走一次，走遍所有的七座桥。,一笔画问题,图1,中国邮路问题 我国数学家管梅谷教授1962年首次提出，并给出了它的解法(奇偶点图上作业法)。 邮递员在送报刊信件时，从邮局出发，一般地每次都要走遍所负责的全部街道，任务完成后返回邮局。那么邮递员应该选择哪一条

2、路线才能以尽可能少的路程走完所有的街道呢？,有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）

3、其中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 相邻边：如果两条边有一个公共端点 环：边的两个端点相同 多重边(平行边)：两个点之间有多于一条边(弧)

4、 多重图: 无环但允许有多重边的图 简单图：无环且无多重边的图 注:在有向图中，如果两点之间有不同方向的两条弧，不是多重边,端点的次d(v)：点 v 作为端点的边的个数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1；悬挂边：与悬挂点连接的边， 孤立点：d(v)=0；空图：E = ，无边图。,在有向图中，以Vi为始点的边数称为Vi的出次，以Vi为终点的边数称为Vi的入次，入次和出次的和称为该点的次。 有向图中所有顶点的入次之和等于所有顶点的的出次之和。,图的连通性： 链：由两两相邻的点及其相关联的边构成的点边序列。如： v0 , e1 , v1 , e2 , v2 ,

5、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分别为链的起点和终点 回路：通路的起点和终点相同 连通图：图中任意两点之间均至少有一条链相连，否则称作不连通图。 任何一个不

6、连通的图都可以分为若干个连同子图，每一个都称为原图的一个分图,例如图中，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 的部分图；,部

7、分图,子图,必须指出，并不是从图G1中任选一些顶点和边在一起就组成G1的子图G1，而只有在G1中的一条边以及连接该边的两个端点均选入G2时，G2才是G1的子图。,真子图,v1,部分图,若T是图G(V，E)的部分图，且T是树，则称T为G的部分树。 若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，也称为G的一个余树。 余树不一定是树！,一个没有圈的图称为一个无圈图或称为林。 一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。,树与部分树,网络 点和边带有某种数量指标的图称为网络，或称为赋权图。,最小树问题：选取网络中的部分图，使得网络连通，且使总权数最小。 在

8、实际应用中，经常碰到需要求一个赋权连通图的最小树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。 求最小树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为破圈法，一种称为取边避圈法。,网络最小树问题,取边避圈法 方法步骤：依次在图中取一个权值最小的边，或者是相对最短的边，并且在每次取边时都不能与已取的边构成圈。 首先在图中选最短的边，并且将与之关联的两个点标记， 然后每次都在标记点和未标记点间可能的边中取一个最短的边，并将新选的边标记， 重复上述

9、过程，直到所有的点均被标记了。,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,欧拉链与欧拉圈 经过且仅经过图中每一条边一次的链称为欧拉链，经过且仅经过图中每一条边一次的圈称为欧拉

10、圈,定理 连通多重图中含有欧拉链的充分必要条件是图中奇点的个数为0或2。且当且仅当没有奇点时图中含有欧拉圈，即没有奇点的连通图必含有欧拉圈。,E=v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5,对于不含奇点的连通图，中国邮路问题就是要找图中的欧拉圈。,v1,v2,v3,v4,v5,v6,含有奇点的连通图中不含欧拉圈，此时，最优的邮递路线是什么呢？,求解中国邮路问题的奇偶点图上作业法,奇偶点表上作业法 (1)找出奇点(一定为偶数个)，在每两个奇点之间找一条链，在这些链经过的所有边上增加一条边，这样所有的奇点变为偶点，一定存在欧拉圈，但是不一定是路线最短的，所以需要检验和调整。

11、(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中的每一条弧(

12、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

13、到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开始，按

14、照第一个标号逆向追踪，直到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次标号的

15、第二个标号值，计算公式如下：,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的产品数量最多。,基本概念,网络

16、与流 对有向图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)为可行流的流量，发点的净输出量

17、等于收点的净输入量。,最大流问题就是要找出一个可行流使得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

18、进行改进；如果没有增广链，则已经得到最大流。,定理：可行流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