运筹学第5章 图与网络

1、n图论的基本概念图论的基本概念n图论在网络分析中的应用图论在网络分析中的应用v 最小树问题最小树问题v 最短路问题最短路问题v 最大流问题最大流问题 1734年年,七桥问题七桥问题(德国哥尼斯堡德国哥尼斯堡)民间流传难题民间流传难题:一个人如何一一个人如何一次走遍七座桥次走遍七座桥且每座桥只走且每座桥只走一次一次?1736年数学家欧拉证年数学家欧拉证明了鉴别准则明了鉴别准则:一笔划一笔划问题问题(欧拉定理欧拉定理)甲甲丙丙丁丁戊戊乙乙图论中图论中的的图与几何图、工程图是不一样图与几何图、工程图是不一样的，图中点的相对位置、点与点之间连的，图中点的相对位置、点与点之间连线的长短曲直，对于反映对象

2、之间的关线的长短曲直，对于反映对象之间的关系并不是重要的。系并不是重要的。 例：补充：补充： 两个定理两个定理qvdVv2)(qvdvdvdVvVvVv2)()()(21Vvvd)(2)(Vvvd2)(Vvvd1)(VvvdV3V4V6V3V4V6V3V4V67、链：在图中，任意两顶点之间可、链：在图中，任意两顶点之间可以构成一条由有限个点与边（弧）组以构成一条由有限个点与边（弧）组成的连续序列，在序列中点与边（弧）成的连续序列，在序列中点与边（弧）交替出现，称这样的一个序列为一条交替出现，称这样的一个序列为一条链。链。 圈：一条封闭的链。圈：一条封闭的链。简单链：只重复点、无重复边简单链：只

3、重复点、无重复边初等链：无重复点、无重复边初等链：无重复点、无重复边8、路：在一条路中，所有弧的方向、路：在一条路中，所有弧的方向均一致。均一致。 回路：一条封闭的路。回路：一条封闭的路。在无向图中，链与路的概念是一致的；在无向图中，链与路的概念是一致的；在有向图中，路一定是链，但链不一定在有向图中，路一定是链，但链不一定是路。是路。连通图与非连通图连通图与非连通图连通图连通图树树在任一图G=（V，E）中，当点集V确定后，树图是G中边数最少的连通图。练习：下图中练习：下图中1表示某生产队的水源地，其它表示某生产队的水源地，其它图形表示水稻田，用堤埂分割为很多小块。图形表示水稻田，用堤埂分割为很

4、多小块。为了用水灌溉，需要挖开一些堤埂。问最少为了用水灌溉，需要挖开一些堤埂。问最少挖开多少堤埂，才能使水浇灌到每小块稻田。挖开多少堤埂，才能使水浇灌到每小块稻田。 123456789101112将水源地及每小块稻田各用一个点来表示，边表示它们之间有堤埂相连，那么连接这些点的树图的边数即为至少要挖开的堤埂数。 如果图如果图G的生成子图的生成子图G是树，则称是树，则称G为为G的生成树。的生成树。若将树作为图的一个子图来考虑若将树作为图的一个子图来考虑例：连通图G生成子图1是一个树生成子图2是一个树生成子图3是一个树生成子图4是一个树生成子图5是一个树 由树的定义可知：图由树的定义可知：图G的生成

5、子图的生成子图1、2、3、4、5都是一棵树，称为支撑树。都是一棵树，称为支撑树。 那么，什么是最小生成树（最小树）呢？那么，什么是最小生成树（最小树）呢？TijwTWmin*)(步骤：步骤：1、先任取一个圈，从圈中去掉一条权最大的边，若在同一个、先任取一个圈，从圈中去掉一条权最大的边，若在同一个圈中有几条都是权最大边，则任选其中的一条边去掉。圈中有几条都是权最大边，则任选其中的一条边去掉。2、在余下的子图中，重复上述步骤，直至没有圈为止。、在余下的子图中，重复上述步骤，直至没有圈为止。避圈法：开始选一条最小权的边，在以后的每一步中，避圈法：开始选一条最小权的边，在以后的每一步中，总从未被选取的

6、边中选一条权最小的边，并使之与已总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈，如果同时有几条都是最小权的边，选取的边不构成圈，如果同时有几条都是最小权的边，则可从中任选一条。则可从中任选一条。23464524练习：上图表示练习：上图表示5个村庄的线路图，每边旁的数字个村庄的线路图，每边旁的数字表示村庄之间线路的长度，现要求沿线路架设有表示村庄之间线路的长度，现要求沿线路架设有线广播线，不仅使各村都能听到有线广播，而且线广播线，不仅使各村都能听到有线广播，而且使广播线总长度最短。使广播线总长度最短。22423423答案：答案：总长为11v1v2v4v3v5v6v7v878234

7、476462231513答案：出现了退化现象。最小元素法求初始方案经过两次调整，计算三次检验数，最后得到了含退化最优解的运输方案：x11=8,x23=4,x24=5,x31=0,x33=1,x32=6; Z*=75运输问题表上作业法步骤举例：运输问题表上作业法步骤举例：（一）最小元素法确定初始调运方案（一）最小元素法确定初始调运方案1221（二）闭回路法计算检验数（二）闭回路法计算检验数（四）闭回路法重新计算检验数（四）闭回路法重新计算检验数1321 再次计算检验数，发现检验数均大于0，于是得到了最优方案。PijwPWmin*)(管道铺设、线路安排、管道铺设、线路安排、 厂区布局、设备更新等。

8、厂区布局、设备更新等。网络中所有的弧权均网络中所有的弧权均 ，即，即 。0ijw ： 标号标号 P P（固定标号或永久性标号）（固定标号或永久性标号）从始点到该标号点的最短路权。从始点到该标号点的最短路权。 标号标号 T T（临时性标号）（临时性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权。4v1v2v3v4v7v6v8456475541v59671v 5127563425527313571练习1：求1275634231351(0)(2)(3)(4)(7)(8)(13)1275634223351(0)(2)(3)(4)(7)(8)(13)4v1v2v3v4v6v5v722561413412步骤步骤 考察点考察点 T标号点集标号点集 标标 号（号（ 表表P标号）标号）1v1v2，v7v1 v2 v3 v4 v5 v6 v7 0 - - - - - - 0+20+5 2 5 - - - - 23456v2v3v4v5v6v3，v7v4，v7v5，v6，v7v5，v72+22+42+6 4 6 8 - -4+14+3 5 8 7 - 5+45+1 5+4 8 6 96+2 8 8v78+18反向追踪，得到最优路线：反向追踪，得到最优路线：v1 v2 v3 v4 v6 v7v552731213