运筹学ch图与网络分析.pptx

《运筹学ch图与网络分析.pptx》由会员分享，可在线阅读，更多相关《运筹学ch图与网络分析.pptx（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1847年 物理学家克希荷夫发表了关于树的第一篇论文1857年 英国数学家凯莱利用树的概念研究有机化合物的分子结构 1878年雪尔佛斯脱首次使用“图”这个名词 1936年匈牙利数学家哥尼格发表了第一本图论专著有限图与无限图的理论20世纪50年代 图论形成了两个本质上不同的发展方向图论系统的理论研究1736年 数学家欧拉发表了关于图的第一篇论文图论的代数方向图论的最优化方向第1页/共57页1736年 瑞士数学家 欧拉（E.Euler)提出“七桥问题”通过每座桥刚好一次又回到原地。是否可以一笔画？第2页/共57页1859年 英国数学家 哈密尔顿(Hamiltonian)用一个规则的实心十二面体，它

2、的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“环球旅行”。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。发明“环球旅行”游戏用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就被称为哈密顿问题。第3页/共57页1850年 英国人格思里提出了“四色猜想”1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿个判断，终于完成了四色定理的证明。任何一个平面图，都可以用四种颜色来染色，使得任何两个相邻的区域有不同的颜色。世界近代

3、三大数学难题之一 格思里和其弟弟格里斯德摩尔根的好友、著名数学家哈密尔顿爵士几百年来，许多数学家致力于这项研究：格思里弟弟的老师、著名数学家德摩尔根英国最著名数学家凯利18781880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。11年后，即1890年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。第4页/共57页例 2 有A、B、C、D、E 五个球队举行比赛，已知A 队与其它各队都比赛过一 次；B 队和A、C 队比赛过；C 队和A、B、D 队赛过；D 队和A、C、E 队比赛过

4、；E 队和A、D 队比赛过。那么：这种比赛关系就可以用图来表示ABCDE点：表示球队点与点之间的连线：表示两球队间比赛过第5页/共57页例3 五个球队之间的比赛结果是：A队胜了B、D、E队；B队胜了C队；C队 胜了A、D队；D队没有胜过；E队胜了D队；用点与点之间带箭头的线描述“胜负关系”关系A队三胜一负B队一胜一负C队两胜一负D队三战三负E队一胜一负从图中可以看出各球队之间比赛情况：ABCDE那么，这种胜负关系该如何用图来描述呢？第6页/共57页10.1 图的基本概念定义一个图G是指一个二元组(V(G),E(G)，即图是由点及点之间的联线所组成。其中:1）图中的点称为图的顶点(vertex)

5、，记为：v2）图中的连线称为图的边(edge)，记为：e vi,vj，vi、vj是边 e 的端点。3）图中带箭头的连线称为图的弧(arc)，记为：a(vi,vj)，vi、vj是弧 a 的 端点。要研究某些对象间的二元关系时，就可以借助于图进行研究第7页/共57页v分类无向图：点集V和边集E构成的图称为无向图(undirected graph)，记为：G(V，E)若这种二元关系是对称的，则可以用无向图进行研究有向图：点集V和弧集A构成的图称为有向图(directed graph)，记为：D(V，A)若这种二元关系是非对称的，则可以用有向图进行研究有限图:若一个图的顶点集和边集都是有限集，则称为有

6、限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.第8页/共57页第9页/共57页第10页/共57页1 图反映对象之间关系的一种工具，与几何图形不同。图反映对象之间关系的一种工具，与几何图形不同。2 图中任何两条边只可能在顶点交叉，在别的地方是立体交叉，不是图的顶点。3 图的连线不用按比例画，线段不代表真正的长度，点和线的位置有任意性。4 图的表示不唯一。如：以下两个图都可以描述“七桥问题”。图的特点：第11页/共57页3 奇点：次为奇数的点。4 偶点：次为偶数的点。5 孤立点：次为零的点。6 悬挂点：次为1的点。1 端点：若e=u，v E，则称u，v 是 e 的端点。2 点的次：

7、以点 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)的概念第12页/共57页例1 G=(V,E)Vv1,v2,v3,v4,v5,v6,v7 Ee1,e2,e3,e4,e5,e6,e7,e8 奇点：v2，v3偶点：v1，v4v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7悬挂点：v5，v6孤

8、立点：v7第13页/共57页如：e1、e2 是多重边。e8 是悬挂边。v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7e7 是环图 G 或 D 中点的个数记为 p(G)或 p(D)，简记为 p图 G 或 D 中边的个数记为 q(G)或 q(D)，简记为 q点的个数p7边的个数q8定理推论 任何图中奇点的个数为偶数第14页/共57页3 初等链（圈）：若链（圈）中各点均不同，则称为初等链（圈）。如：v1,e1,v2,e3,v3 4 简单链（圈）：若链（圈）中各边均不同，则称为间单链（圈）。1 链：一个点、边的交替的连续序列vi1,ei1,vi2,ei2,vik,eik称为链，记为。2

9、圈(cycle)：若链的 vi1vik，即起点终点，则称为圈。链(chain)的概念v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7 v1,e1,v3,e4,v4：链初等链简单链不是链 v1,e1,v2,e3,v3,e6,v1 圈初等圈间单圈圈一定是链，链不一定是圈第15页/共57页路路PATH路(path)：顶点和边均互不相同的一条途径。若在有向图中的一个链中每条弧的方向一致，则称为路。（无向图中的路与链概念一致。）回路(circuit)：若路的第一个点与最后一个点相同，则称为回路。连通性:点i和j点是连通的：G中存在一条（i，j）路G是连通的：G中任意两点都是连通的 路一定是链

10、，但链不一定是路第16页/共57页 例 在右边的无向图中：途径或链：迹或简单链：路或路径：圈或回路：v1v2v3v4e1e2e3e4e5e6 v1,e1,v2,e3,v3 链不是路 v1,e2,v2,e3,v3 链且是路 v1,e2,v2,e1,v1 链是回路 注意区别：环、圈、回路的概念在右边的有向图中：第17页/共57页连通图(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)是多重图v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7连通图第18页/共57页10.2 树（tree）一、树的定义树：一个无圈的连通图称为树。例：红楼梦中贾府人物之间的血统关系树贾演贾源贾代化贾代善贾放贾敷贾珍贾蓉贾赦贾政贾琏贾宝玉贾环贾珠贾兰（宁国府）（荣国府）第19页/共57页二、树的性质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)是树 任意两个顶点之间恰有一条链。第20页/共57页图的支撑树(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)的子集E

13、E。特点边少、点不少。第21页/共57页1 最小树定义如果T(V，E)是 G 的一个支撑树，称 T 中所有边的权之和为支撑树T的权，记为W（T），即：若支撑树T*的权W（T*）是G的所有支撑树的权中最小者，则称T*是G 的最小支撑树（最小树），即：W（T*）min W(T)最小树(minimum spanning tree)问题第22页/共57页例8：1）破圈法：在图G中任取一个圈，从圈中去掉权数最大的边，对余下的图重复这个 步骤，直到G中不含圈为止，即可得到 G 的一个最小树。2 2 求最小树的算法（求最小树的算法（minimum spanning tree minimum spanning

14、 tree algorithmalgorithm）v2v14v3v4v53532142且p5 q4 1）在圈 v1v2v3v1中去掉v1,v32）在圈 v2v4v3v2中去掉v2,v33）在圈 v2v4v5v2中去掉v2,v54）在圈 v3v4v5v3中去掉v3,v5图中已经不含圈 已经求出了最小树 W(T*)42129 第23页/共57页避圈法是一种选边的过程，其步骤如下：1.从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中第24页/共57页用避圈法解用避圈法解v5v1v3v6v4v2v7255233575711

15、最小部分树如图上红线所示；最小权和为14。思考：破圈法与必避圈法各自的思路是怎样做的呢？见圈就破，去掉其中权最大的。加边取其中最小的。第25页/共57页例8 要在5个城市架设电话线，使城镇之间能够通话两镇直接连接，每两个城镇之 间的架设电话线的造价如下图所示，各边上的数字为造价（单位：万元）。问：应如何架线，可使总造价最小？v1v3v2v5v4v6v7252463112424第26页/共57页解：v1v3v2v5v4v6v72524631124241 破圈法：2 避圈法：v1v3v2v5v4v6v7252463112424总造价：W(T*)22112210（万元）第27页/共57页本节重点及难

16、点重点难点1 图的概念及性质4 树的概念及性质5 部分树及最小树 2 点的概念及性质3 链的概念及性质1 图的概念及性质4 部分树及最小树 2 点的概念及性质3 链的概念及性质第28页/共57页10.3最短路问题 最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路.第29页/共57页 例 如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交 通网到达v6，

17、要寻求总路 程最短的线 路。v6v5v3v1v4v2365112436最短路径问题最短路径问题 第30页/共57页 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).第31页/共57页 给定一个赋权有向图D(V，A),对每一条弧aijw(vi，vj)，相应地有权w(aij)=wij，又有两点vs、vt V,设 p 是 D 中从

18、vs 到vt 的一条路，路 p 的权是 p 中所有弧的权之和,记为w(p)最短路问题就是求从vs 到vt 的路中一条权最小的路 p*:最短路径问题最短路径问题 第32页/共57页10.3 10.3 最短路径问题最短路径问题 下面仅介绍在一个赋权有向图中寻求最短路的方法双双标标号号法法（Dijkstra算法），它是在1959年提出来的。目前公认，在所有的权wij 0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。二、最短路问题的算法二、最短路问题的算法 方法：标号法（Dijkstra，1959）给每点vj标号dj，vi。其中dj为

19、v1至vj的最短距，vi为最短路上Vj的前一点。第33页/共57页标号法步骤：第34页/共57页例 求v1到v6的最短路。44，V2V2 5 5，V1V1 55，V3V3 33，V1V1 77，V5V599，V2V288，V3V3 1010，V4V4 11 11，V5V5（1）首先将v1赋给VS。给V1以P标号，d(v1)0，vs=V1（2）考察V1的关联边，选最小权的边的端点加以标号 0,V10,V1v6v5v3v1v4v236511243610.3 10.3 最短路径问题最短路径问题 第35页/共57页用标号法解例3v5v1v3v6v4v2v72552335757110，v12，v13，v

20、1其中2=min0+2,0+5,0+3其中3=min0+3，0+5，2+2，2+74，v27，v38，v513，v6最短距为13；4，v4最短路有2条为v1-v2-v3-v5-v6-v7 和v1-v4-v3-v5-v6-v7。第36页/共57页最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元)：年号 1 2 3 4 5 价格22.12.32.42.6 汽车使用年龄0112233445维修费用0.71.11.522.5试用网络分析中求最短路的方法确定公司可采用的最优策略。方法：以年号作顶点绘图，连线表示连续使用期间，以 费用作

21、路长。第37页/共57页1345622.73.85.37.39.82.87.43.95.43.13.34.23.04.15.62.7,13.8,17.9,39.4,35.3,1第38页/共57页P284 10.4（a）10.7 作 业 第39页/共57页10.4 最大流问题 v 流量问题在实际中是一种常见的问题。如公路系统中有车辆流量问题，供电系统中有电流量问题等等。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。网络赋权图，记D=（V，E，C），其中C=c1，cn，ci为边ei上的权（设ci ）。网络分析主要内容最小部分树、最短路、最大流。第40

22、页/共57页1.问题 已知网络D=（V，A，C），其中V为顶点集，A为弧集，C=cij为容量集，cij 为弧（vi，vj）上的容量。现D上要通过一个流f=fij，其中fij 为弧（vi，vj）上的流量。问应如何安排流量fij可使D上通过的总流量v最大？例如：v4v2vsv1vtv3213145325第41页/共57页2.数学模型（容量约束）（平衡条件）问题：最大流问题的决策变量、目标函数、约束条件各是什么？第42页/共57页3.基本概念与定理如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（

23、1，1）（4，3）（5，1）（3，0）（2，1）（5，3）第43页/共57页（2）可增值链（增广链）v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）第44页/共57页（3）截集与截量截量：截集上的容量和，记为 。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）例4 对于下图，若V1=vs，v1，请指出相应的截集与截量。第45页/共57页例4 对于下图，若V1=vs，v1，请指出相应的截集与截量。解：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（

24、4，3）（5，1）（3，0）（2，1）（5，3）第46页/共57页（4）流量与截量的关系截集上的流量和相应于截集的反向弧上流量和最大流最小割定理：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）第47页/共57页4.解法（5）最大流的判别条件第48页/共57页步骤：第49页/共57页第50页/共57页例5 用标号法求下面网络的最大流。解：第一次标号及所得可增值链如图，调量 =1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量v=5，同时得最小截v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）

25、（4，3）（5，1）（3，0）（2，1）（5，3）2020第51页/共57页最大流问题的应用例子（1）汽车由A城通往B城的可能的路线如下图所示。环境保护部门拟建立足够数量的汽车尾气检查站，以便使每辆汽车至少必须经过一个检查站。建立检查站的费用根据各路段的条件而有所不同(如图上数字所示)。若求这个问题的最小费用解，可使用 模型。a.最短路模型；b.最大流模型；c.最小支撑树模型AacbdefgB824452643367378第52页/共57页某汽车公司有两家汽车配件制造厂A和B，负责向两个服务配送中心C和D供应汽车配件。运送的道路网络及各路段的允许通过容量如下图所示。假设配件厂的供应量无限制。求

26、向C、D的供应量最大的运送方案和相应的最大供应量。AB1234567CD60205070403050406030402010408070st求解：最大流模型10020060160最大流问题的应用例子（2）第53页/共57页AB1234567CD60205070403050406030402010408070st100200601601。确定从s到t的可行流（观测法）6016070801020403030606030407030302040801402。确定从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第54页/共57页P285 11.12作 业 某个城市的街道图如下图，图上数字为道路的最大通行能力。求从S到T的最大流，如果要提高S到T的车流量，应首先改扩哪几条道路？STABC101510152020515第55页/共57页第56页/共57页57感谢您的观看！第57页/共57页