《运筹学课件ch10图与网络分析.ppt》由会员分享，可在线阅读，更多相关《运筹学课件ch10图与网络分析.ppt（58页珍藏版）》请在三一文库上搜索。
1、第十章,图与网络分析 Graph & Network Analysis,章节大纲,图的基本概念 树与最小支撑树的应用 最短路问题 网络最大流问题 最小费用最大流问题,1847年 物理学家克希荷夫发表了关于树的第一篇论文,1857年 英国数学家凯莱利用树的概念研究有机化合物的分子结构,1878年雪尔佛斯脱首次使用“图”这个名词,1936年匈牙利数学家哥尼格发表了第一本图论专著有限图与无限图的理论,20世纪50年代 图论形成了两个本质上不同的发展方向,图论系统的理论研究,1736年 数学家欧拉发表了关于图的第一篇论文,图论的代数方向,图论的最优化方向,1736年 瑞士数学家 欧拉（E. Euler
2、) 提出“七桥问题” 通过每座桥刚好一次又回到原地。,是否可以 一笔画？,1859年 英国数学家 哈密尔顿(Hamiltonian),用一个规则的实心十二面体，它的20个顶点标出世界 著名的20个城市，要求游戏者找一条沿着各边通过每 个顶点刚好一次的闭回路，即 “环球旅行” 。, 由于运筹学、计算机科学和编码理论中的很多 问题都可以化为哈密顿问题，从而引起广泛的注意和 研究。, 发明“环球旅行”游戏,用图论的语言来说，游戏的目的是在十二面体的图中 找出一个生成圈。这个问题后来就被称为哈密顿问题。,1850年 英国人格思里提出了“四色猜想”,1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的
3、两台不同的电子计算机上， 用了1200个小时，作了100亿个判断，终于完成了四色定理的证明。,任何一个平面图，都可以用四种颜色来染色，使得任何两个相邻的区域有不同的颜色。, 世界近代三大数学难题之一,格思里和其弟弟格里斯,德摩尔根的好友、著名数学家哈密尔顿爵士,几百年来，许多数学家致力于这项研究：,格思里弟弟的老师、著名数学家德摩尔根,英国最著名数学家凯利,18781880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四 色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。,11年后，即1890年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。,不久，泰勒的证明
4、也被人们否定了。,例 2 有A、B、C、D、E 五个球队举行比赛，已知A 队与其它各队都比赛过一 次；B 队和A、C 队比赛过；C 队和A、B、D 队赛过； D 队和A、C、E 队比赛过；E 队和A、D 队比赛过。,那么：这种比赛关系就可以用图来表示,A,B,C,D,E,点：表示球队,点与点之间的连线：表示两球队间比赛过,例3 五个球队之间的比赛结果是：A队胜了B、D、E队； B队胜了C队； C队 胜了A、D队； D队没有胜过；E队胜了D队；, 用点与点之间带箭头的线描述“胜负关系”关系,从图中可以看出各球队之间比赛情况：,A,B,C,D,E,那么，这种胜负关系该如何用图来描述呢？,10.1
5、图的基本概念,定义 一个图G是指一个二元组(V(G),E(G)，即图是由点及点之间的联线所组成。其中:,1）图中的点称为图的顶点(vertex)，记为：v,2）图中的连线称为图的边(edge)，记为：e vi, vj，vi、vj是边 e 的端点。,3）图中带箭头的连线称为图的弧(arc)，记为：a (vi, vj)，vi、vj是弧 a 的 端点。, 要研究某些对象间的二元关系时，就可以借助于图进行研究,分类 无向图：点集V和边集E构成的图称为无向图(undirected graph)，记为： G(V，E) 若这种二元关系是对称的，则可以用无向图进行研究 有向图：点集V和弧集A构成的图称为有向图
6、(directed graph) ，记为：D(V，A) 若这种二元关系是非对称的，则可以用有向图进行研究 有限图: 若一个图的顶点集和边集都是有限集，则称为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.,1 图反映对象之间关系的一种工具，与几何图形不同。,2 图中任何两条边只可能在顶点交叉，在别的地方是立体交叉，不是图的顶点。,3 图的连线不用按比例画，线段不代表真正的长度，点和线的位置有任意性。,4 图的表示不唯一。如：以下两个图都可以描述“七桥问题”。,图的特点：,3 奇点：次为奇数的点。,4 偶点：次为偶数的点。,5 孤立点：次为零的点。,6 悬挂点：次为1的点。,1
7、端点：若e =u，v E，则称u，v 是 e 的端点。,2 点的次：以点 v 为端点的边的个数称为点 v 的次，记为：d(v)。 在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或 dG(v). 在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的度或次数,点(vertex)的概念,例1 G =(V, E),Vv1, v2, v3, v4 , v5 , v6 , v7 ,Ee1, e2, e3, e4 , e5 , e6 , e7 , e8
8、 ,奇点：v2，v3,偶点：v1，v4,悬挂点：v5，v6,孤立点：v7,如：e1、e2 是多重边。,e8 是悬挂边。,e7 是环,图 G 或 D 中点的个数记为 p(G) 或 p(D) ，简记为 p,图 G 或 D 中边的个数记为 q(G) 或 q(D)，简记为 q,点的个数p7,边的个数q8,定理,推论 任何图中奇点的个数为偶数,3 初等链（圈）：若链（圈）中各点均不同，则称为初等链（圈） 。,如：, v1, e1, v2, e3, v3 ,4 简单链（圈） ：若链（圈）中各边均不同，则称为间单链（圈） 。,1 链：一个点、边的交替的连续序列vi1, ei1, vi2, ei2, , vi
9、k, eik称为链，记为。,2 圈(cycle)：若链的 vi1vik，即起点终点，则称为圈。,链(chain)的概念, v1, e1, v3, e4, v4 ,：,链,初等链,简单链,不是链, v1, e1, v2, e3, v3 , e6 , v1 ,圈,初等圈,间单圈,圈一定是链，链不一定是圈,路PATH,路(path)：顶点和边均互不相同的一条途径。 若在有向图中的一个链中每条弧的方向一致，则称为路。（无向图中的路与链概念一致。） 回路(circuit)：若路的第一个点与最后一个点相同，则称为回路。 连通性: 点i和j点是连通的：G中存在一条（i，j）路 G是连通的：G中任意两点都是连
10、通的, 路一定是链，但链不一定是路,例 在右边的无向图中：,途径或链：,迹或简单链：,路或路径：,圈或回路：, v1, e1, v2, e3, v3 ,链,不是路, v1, e2, v2, e3, v3 ,链,且是路, v1, e2, v2, e1, v1 ,链,是回路, 注意区别：环、圈、回路的概念,在右边的有向图中：,连通图(connected graph)：若图中任何两点间至少有一条链，则称为连通图 。否则， 为不连通图。,简单图(simple graph)：一个无环、无多重边的图称为间单图。,多重图(multiple graph)：一个无环，但有多重边的图称为多重图。,连通分图：非连通
11、图的每个连通部分称为该图的连通分图。,基础图：去掉有向图中所有弧上的箭头，得到的图称为原有向图的基础图。,图G(V, E)为不连通图,但G(V, E)是G的连通分图 其中：Vv1, v2, v3, v4 Ee1, e2, e3, e4, e5, e6, e7,图G(V, E)是多重图,连通图,10.2 树（tree）,一、树的定义,树：一个无圈的连通图称为树。,例：红楼梦中贾府人物之间的血统关系树,贾演,贾源,贾代化,贾代善,贾放,贾敷,贾珍,贾蓉,贾赦,贾政,贾琏,贾宝玉,贾环,贾珠,贾兰,（宁国府）,（荣国府）,二、树的性质,1 设图G(V, E)是一个树，点数P(G) 2，则 G 中至少
12、有两个悬挂点。,2 图G(V，E)是一个树G不含圈，且恰有p-1条边（p是点数）。,3 图G(V，E)一个树 G 是连通图，且q(G)p(G)1 （q是边数）。,4 图G(V，E)是树 任意两个顶点之间恰有一条链。,图的支撑树(spanning tree),1 支撑子图：设图G(V，E)，图G(V，E)的VV，E E，则称G是G的一个 支撑子图。,2 支 撑 树：设图T(V，E)是图G(V，E)的支撑子图，如果T(V，E)是一个树， 则称 T 是 G 的一个支撑树。,如何寻找 “支撑树” 呢？, 图G(V，E)的点集与图G(V，E)的点集相同，VV，但图G(V，E) 的边集仅是图G(V，E)的
13、子集E E。,特点边少、点不少。,1 最小树定义,如果T(V，E)是 G 的一个支撑树，称 T 中所有边的权之和为支撑树T的权， 记为W（T），即：,若支撑树T* 的权W（T*）是G的所有支撑树的权中最小者， 则称T* 是G 的最小 支撑树（最小树）， 即：W（T*） min W(T),最小树(minimum spanning tree)问题,例8：,1） 破圈法：在图G中任取一个圈，从圈中去掉权数最大的边，对余下的图重复这个 步骤， 直到G中不含圈为止，即可得到 G 的一个最小树。,2 求最小树的算法（minimum spanning tree algorithm）,且p5 q4,1）在圈
14、v1v2v3v1中去掉v1,v3,2）在圈 v2v4v3v2中去掉v2,v3,3）在圈 v2v4v5v2中去掉v2,v5,4）在圈 v3v4v5v3中去掉v3,v5,图中已经不含圈, 已经求出了最小树,W(T*)42129,避圈法是一种选边的过程，其步骤如下：,1. 从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；,2. 把顶点集V分为互补的两部分V1, 1 ，其中,用避圈法解,最小部分树如图上红线所示； 最小权和为14。,思考：破圈法与必避圈法各自的思路是怎样做的呢？,见圈就破，去掉其中权最大的。 加边取其中最小的。,例8 要在5个城市架设电话线，使城镇之
15、间能够通话两镇直接连接，每两个城镇之 间的架设电话线的造价如下图所示，各边上的数字为造价（ 单位：万元 ）。 问：应如何架线，可使总造价最小？,解：,1 破圈法：,2 避圈法：,总造价：W(T*)22112210 （万元）,本节重点及难点,重点,难点,1 图的概念及性质,4 树的概念及性质,5 部分树及最小树,2 点的概念及性质,3 链的概念及性质,1 图的概念及性质,4 部分树及最小树,2 点的概念及性质,3 链的概念及性质,10.3最短路问题,最短路问题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,用流等问题,都可通过建立最短路问题模型来求解.,1) 求赋权
16、图中从给定点到其余顶点的最短路.,2) 求赋权图中任意两点间的最短路.,例 如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交 通网到达v6， 要寻求总路 程最短的线 路。,最短路径问题,2) 在赋权图G中，从顶点u到顶点v的具有最小权,定义 1) 若H是赋权图G的一个子图，则称H的各,边的权和 为H的权. 类似地，若,称为路P的权,若P(u,v)是赋权图G中从u到v的路,称,的路P*(u,v)，称为u到v的最短路,3) 把赋权图G中一条路的权称为它的长，把(u,v),路的最小权称为u和v之间的距离，并记作 d(u,v).,给定一个赋权有向图D
17、 ( V，A ) ,对每一条弧aijw (vi，vj)，相应地有权w (aij )= wij ，又有两点vs、vt V,设 p 是 D 中从vs 到vt 的一条路，路 p 的权是 p 中所有弧的权之和,记为w(p)最短路问题就是求从vs 到vt 的路中一条权最小的路 p*:,最短路径问题,10.3 最短路径问题,下面仅介绍在一个赋权有向图中寻求最短路的方法双标号法（Dijkstra算法），它是在1959年提出来的。目前公认，在所有的权wij 0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。,二、最短路问题的算法,方法：标号法（
18、Dijkstra，1959） 给每点vj标号dj，vi。 其中dj为v1至vj的最短距，vi为最短路上Vj的前一点。,标号法步骤：,例 求v1到v6的最短路。, 4，V2 5，V1, 5，V3, 3，V1, 7，V5 9，V2 8，V3, 10，V4 11，V5,（1）首先将v1赋给VS。给V1以P标号，d(v1)0，vs=V1 （2）考察V1的关联边，选最小权的边的端点加以标号, 0,V1,10.3 最短路径问题,用标号法解例3,0，v1,2，v1,3，v1,其中2=min0+2,0+5,0+3,4，v2,7，v3,8，v5,13，v6,最短距为13；,4，v4,最短路有2条为v1-v2-v
19、3-v5-v6-v7 和v1-v4-v3-v5-v6-v7。,最短路问题的应用例子,某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元)： 年号 1 2 3 4 5 价格 2 2.1 2.3 2.4 2.6 汽车使用年龄 01 12 23 34 45 维修费用 0.7 1.1 1.5 2 2.5 试用网络分析中求最短路的方法确定公司可采用的最优策略。,方法：以年号作顶点绘图，连线表示连续使用期间，以 费用作路长。,1,3,4,5,6,2,2.7,3.8,5.3,7.3,9.8,2.8,7.4,3.9,5.4,3.1,3.3,4.2,3.0,4.1,
20、5.6,2.7, 1,3.8, 1,7.9, 3,9.4, 3,5.3, 1,P284 10.4（a）10.7,作 业,10.4 最大流问题,流量问题在实际中是一种常见的问题。如公路系统中有车辆流量问题，供电系统中有电流量问题等等。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。,网络赋权图，记D=（V，E，C），其中C=c1，cn， ci为边ei上的权（设ci ）。 网络分析主要内容最小部分树、最短路、最大流。,1. 问题 已知网络D=（V，A，C），其中V为顶点 集，A为弧集，C=cij为容量集， cij 为弧（vi，vj ） 上的容量。现D上
21、要通过一个流f=fij，其中fij 为弧 （vi，vj ）上的流量。问应如何安排流量fij可使D上 通过的总流量v最大？,2. 数学模型,（容量约束） （平衡条件）,问题：最大流问题的决策变量、目标函数、约束条件各是什么？,3. 基本概念与定理,如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。,（2）可增值链（增广链）,（3） 截集与截量,截量：截集上的容量和，记为 。,例4 对于下图，若V1=vs，v1，请指出相应的截集与截量。,例4 对于下图，若V1=vs，v1，请指出相应的截集与截量。,解：,（4） 流量与截量的关系,截集上的流量和,相应
22、于截 集的反向 弧上流量和,最大流最小割定理：,4. 解法,（5） 最大流的判别条件,步骤：,例5 用标号法求下面网络的最大流。,解：第一次标号及所得可增值链如图，调量 =1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量v=5，同时得最小截,最大流问题的应用例子（1）,汽车由A城通往B城的可能的路线如下图所示。环境保护部门拟建立足够数量的汽车尾气检查站，以便使每辆汽车至少必须经过一个检查站。建立检查站的费用根据各路段的条件而有所不同(如图上数字所示)。若求这个问题的最小费用解，可使用 模型。 a. 最短路模型； b.最大流模型； c.最小支撑树模型,A,a,c,b,d,
23、e,f,g,B,8,2,4,4,5,2,6,4,3,3,6,7,3,7,8,某汽车公司有两家汽车配件制造厂A和B，负责向两个服务配送中心C和D供应汽车配件。运送的道路网络及各路段的允许通过容量如下图所示。假设配件厂的供应量无限制。求向C、D的供应量最大的运送方案和相应的最大供应量。,求解：最大流模型,100,200,60,160,最大流问题的应用例子（2）,100,200,60,160,1。确定从s到t的可行流（观测法）,60,160,70,80,10,20,40,30,30,60,60,30,40,70,30,30,20,40,80,140,2。确定从s到t的最小割（截集） 标号集s,A,B，2，4 未标号集1,3,5,6,7,c,D,t,割集: (a,1)(2,6)(b,3)(4,7) 割量：60+60+70+30=220,此时已找到最大流，即此可行流就是最佳的运送方案。C、D的供应量分别为60和160,P285 11.12,作 业,某个城市的街道图如下图，图上数字为道路的最大通行能力。求从S到T的最大流，如果要提高S到T的车流量，应首先改扩哪几条道路？,Thank You !,