运筹学11-图与网络.ppt

1、第十一章 图与网络规划Graph Theory and Network Analysis,11.1 图与网络的基本概念 11.2 最短路问题 11.3 网络最大流问题 11.4 最小费用最大流问题,内容简介,是近几十年来运筹学领域中发展迅速、而且十分活跃的一个分支 对实际问题的描述具有直观性 广泛应用于物理学、化学、信息论、控制论、计算机科学、社会科学以及现代经济管理科学等许多科学领域 图与网络分析的内容十分丰富本章只介绍图与网络的基本概念以及图论在路径问题、网络流问题等领域中的应用重点讲明方法的物理概念、基本原理及计算步骤,11.1 图与网络的基本概念,图的理论研究已有200多年的历史了早期

2、图论与“数学游戏”有着密切关系所谓“哥尼斯堡七桥”问题就是其中之一,200多年前的东普鲁士有一座哥尼斯堡城，城中有一条河叫普雷格尔河，河中有两个岛屿共建七座桥平时城中居民大都喜欢来这里散步，并提出这样一个问题：一个散步者能否经过每座桥恰恰一次再回到原出发点,11.1 图与网络的基本概念,当时有许多人都探讨了这个问题，但不得其解 著名数学家欧拉（Euler）将这个问题简化为一个如右图所示图形图4个点A、B、C、D表示两岸和小岛两两点间连线表示桥,11.1 图与网络的基本概念,于是问题转化为一笔画问题，即能否从某一点开始一笔画出这个图形，不许重复，最后回到原出发点 欧拉否定了这种可能性 原因是图中

3、与每一个点相关联的线都是奇数条 为此他写下了被公认为世界第一篇有关图论方面的论文（1736年）,11.1 图与网络的基本概念,1859年哈密尔顿提出了另一种游戏：在一个实心的12面体（见图）的20个顶点上标以世界上著名的城市名称，要求游戏者从某一城市出发，遍历各城市恰恰一次而返回原地，这就是所谓“绕行世界问题”,11.1 图与网络的基本概念,作图，此问题变成在从某一点出发寻找一条路径，过所有20个点仅仅一次，再回到出发点 解决这个问题可以按序号1234一一201所形成的一个闭合路径，并称此路径为哈密尔顿圈 具有哈密尔顿圈的图称为哈密尔顿图,11.1 图与网络的基本概念,由此可见，图论中所研究的

4、图是由实际问题抽象出来的逻辑关系图 这种图与几何中的图形和函数论中所研究的图形是不相同的 这种图的画法具有一定的随意性，在保持相对位置和相互关系不变的前提下，点的位置不一定要按实际要求画，线的长度也不一定表示实际的长度而且画成直线或曲线都可以 通俗地说，这种图是一种关系示意图,11.1 图与网络的基本概念,图的概念 所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为E，则图可以表示为：G（V，E），点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。 在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。

5、,图的表示,点与边,顶点数 集合V中元素的个数，记作p(G)。 边数 集合E中元素的个数，记作q(G)。 若e=u,vE，则称u和v为e的端点，而称e为u和v的关联边，也称u，v与边e相关联。 例如图中的图G，p(G)=6，q(G)=9， v1，v2是e1和e2的端点，e1和e2都是v1和v2的关联边。,点边关系,若点u和v与同一条边相关联，则u和v为相邻点；若两条边ei和ej有同一个端点，则称ei与ej为相邻边。 例如在图中v1和v2为相邻点， v1和v5不相邻；e1与e5为相邻边，e1和e7不相邻。,简单图,若一条边的两个端点是同一个顶点，则称该边为环；又若两上端点之间有多于一条边，则称为

6、多重边或平行边。 例如图的e8为环，e1，e2为两重边，e4，e5也是两重边。 含有多重边的图称作多重图。 无环也无多重边的图称作简单图。,图的次,次 点v作为边的端点的次数，记作d(v)，如图中，d(v1)=5, d(v4)=6等 端点次为奇数的点称作奇点；次为偶数的点称作偶点。 次为1的点称为悬挂点，与悬挂点连接的边称作悬挂边； 次为0的点称为孤立点。 图中的点v5即为悬挂点，边e9即为悬挂边，而点v6则是弧立点。,定理,若图G中所有点都是孤立点，则称图G为空图。 定理1 所有顶点的次的和，等于所有边数的2倍。即,定理2 在任一图中，奇点的个数必为偶数。 设V1和V2分别是图G中次数为奇数

7、和偶数的顶点集合。由定理1有,链,由两两相邻的点及其相关联的边构成的点边序列称为链。 v0称为链的起点， vn称为链的终点。 若v0 vn则称该链为开链，反之称为闭链或回路。,简单链,若链中所含的边均不相同，则称为简单链；若点均不相同，则称为初等链或通路。 除起点和终点外点均不相同的闭链，称为初等回路或称为圈。 例如图中,是一条链，且是开链，也是简单链，但不是初等链，因为v1出现两次。,圈,若链中所含的边均不相同，则称为简单链；若点均不相同，则称为初等链或通路。除起点和终点外点均不相同的闭链，称为初等回路或称为圈。 例如图中,是一个圈。,连通性,若一个图G的任意两点之间均至少有一条通路（初等链

8、）连接起来，则称这个图G是一个连通图，否则称作不连通图。 例如图中，v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。,连通的意义,连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。,子图,子图的定义 设， G1=(V1,E1), G2=(V2,E2)，如果V1V2 ，又E1E2 ，则称G1是G2的子图。,必须指出，并不是从图G2中任选一些顶点和边在一起就组成G2的子图G1，而只有在G2中的一条边以及连接该边的两个端点均选入G1时，G1才是G2的子图。,特殊子图,当G

9、1中不包含G2中所有的顶点和边，则称G1是G2的真子图。 部分图 若V1=V2，E1E2 ，则称G1为G2的一个部分图。 若V1V2 ， E1= u,v | uV1, vV1，则称G1是G2中 由V1导出的导出子图。,有向图,在有些图中，边是没有方向的，即u,v=v,u，这种图称为无向图。 而有些关系是不对称的，例如父子关系、上下级关系、加工工序的先后顺序等都具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。 从顶点u指向的弧a，记作a=(u,v),(u,v)(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。仍以V表示点的集合，以A表示弧的集

10、合，则有向图表示为D（V，A）,有向图例,有向图的链路,有向图中，在不考虑边的方向时，也可以相同地定义链，若有向图D（V，A）中，P是一个从u到v的链，且对P中每一条弧而言，在序列中位于该弧前面的点恰好是其起点，而位于该弧后面的点恰好是其终点，这个链P就称为是D中从u到v的一条路。 当路的起点与终点相同，即u=v时，称作一条回路。 顶点全不相同的路称为初等路。 除起点和终点外点均不相同的回路称为初等回路。,树及最小树问题,任何树至少有一个悬挂节点,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果树的节点个数为m，则边的个数为m-1,树中任意两个节点之间只有唯一的一条链,在树的任

11、意两个不相邻的节点之间增加一条边，则形成唯一的圈,树及最小树问题,一个没有圈的图称为一个无圈图或称为林。 一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。 定理 以下关于树的六种不同描述是等价的： 无圈连通图。 无圈，q=p-1。 连通，q=p-1。 无圈，但若任意增加一条边，则可得到一个且仅一个圈。 连通，但若任意舍弃一条边，图便不连通。 每一对顶点之间有一条且仅有一条链。,网络概念,图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。 网络 赋权的图 权 程度的度量，数量描述。,网络概念,节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i

12、，j）,路径（Path） 前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4),4,2,3,1,4,2,3,1,网络由节点和边组成,网络概念,回路（Circuit） 起点和终点重合的路径称为回路 =(1,2),(2,4),(4,1) 回路中各条边方向相同,4,2,3,1,链（Chain） 前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4),4,2,3,1,网络概念,连通图 任意两个节点之间至少有一条链的图称为连通图,2,4,3,5,1,圈(Cycle) 起点和终点重合的链称为圈 =(1,2),(2,4),(3,4),(1,3) 圈中各条边方向不一定

13、相同,4,2,3,1,树(Tree) 无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点,网络概念,平面图(planar graph)，若在平面上可以画出该图而没有任何边相交 走过图中所有边且每条边仅走一次的闭行走称为欧拉回路 定理 ：偶图一定存在欧拉回路(一笔画定理) 图中都是偶点的图称为偶图(even graph),哈密尔顿回路( Hamiltonian circuit)问题,连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中所有的点。显然哈密尔顿回路有且只有 n 条边，若|V|=n 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是由爱尔兰数学家哈密尔顿1859年提出

14、的，但至今仍未解决 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题 搜索哈密尔顿回路的难度是 NP-complete 任两点间都有边的图称为完全图(或全连接图) 完全图中有多少个不同的哈密尔顿回路？ (n1)!/2 完全图中有多少个边不相交的哈密尔顿回路？ (n1)/2 最小哈密尔顿回路问题 (NP-complete) 哈密尔顿路径：包含图中所有点的路径 为什么说找两点间的最长路是非常困难的问题？,中国邮递员问题,中国邮递员问题(Chinese Postman Problem, CPP)是由我国管梅谷教授于1962年首先提出并发表的 问题是从邮局出发，走遍邮区的所有街道至少一次

15、再回到邮局，走什么路由才能使总的路程最短？ 如果街区图是一个偶图，根据定理 3，一定有欧拉回路，CPP问题也就迎刃而解了 若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点 显然要在奇次点间加重复边 如何使所加的边长度最少 归结为求奇次点间的最小 匹配( minimum weighted match) 由Edmons 给出多项式算法(1965),旅行推销员问题(Traveling Salesman Problem),TSP：设v1, v2, .,vn 为 n 个已知城市，城市之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城市一次且仅一次又回到出发点，并使总旅程最短 这种不允

16、许点重复的旅行推销员问题就是最小哈密尔顿回路问题 一般旅行推销员问题(GTSP)：允许点重复的TSP 典型的应用： 乡邮员的投递路线 邮递员开邮箱取信的路线问题 邮车到各支局的转趟问题 运钞 送奶、送水 .,网络最短树问题,最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。 在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。 求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一

17、种称为破圈法，一种称为避圈法,11.2 最短路问题,最短路问题的一般提法是：欲寻找网络中从起点1到终点n的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。 最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题。,最短路问题的Dijkstra算法(双标号法）,步骤： 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合 3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则

18、vs到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。 4. 对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。,例1 求下图中v1到v6的最短路 解：采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：,例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的

19、交通图。权数表示两地间公路的长度（单位：公里）。 解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。,例2最终解得： 最短路径v1 v3 v5 v6 v7，每点的标号见下图,（0,s） V1 （甲地）,15,17,6,2,4,4,3,10,6,5,(13,3) v2,(22,6) V7 （乙地）,V5 (14,3),V6 (16,5),

20、V3 (10,1),V4 (18,5),例3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。 已知：设备每年年初的价格表 设备维修费如下表,例3的解：将问题转化为最短路问题，如下图： 用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的 设备一直使用到第j年年初。 把所有弧的权数计算如下表：,(继上页) 把权数赋到图中，再用Di

21、jkstra算法求最短路。 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1 -v3-v6和 v1-v4-v6,11.4 网络最大流问题,所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定： 网络有一个起点s和一个终点t 网络是有向网络，即流有方向性。 在网络各条弧上都有一个权，表示允许流过的最大流量。若以bij表示由i到j的弧上允许流过的最大流量，以xij表示实际流过该弧的流量，则0 xij bij 网络中，除起点s和终点t之外的任何顶点，流入量总和应该等于流出量的总和。,一、最大流问题的数学模型,二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和 (b)、(c)和(d)的意义相同。,vi,vj,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,求最大流的基本算法 （1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。 （2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。 （3）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量