管理运筹学 第6章 图与网络模型

第六章图与网络模型第六章图与网络模型6.1.图与网络的基本知识6.2.最短路问题6.3.最小树问题6.4.最大流问题ACDB哥尼斯堡七桥问题18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。河中的小岛C与河岸A、对岸B各有两座桥相连接，河中两支流之间的陆地D与A、B、C各有一座桥相连接。当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题。这就是著名的七桥问题1857年，哈密尔顿，实心12面体，20个顶点-环球旅行中国邮递员问题CABD例1：有A、B、C、D、E五个球队，它们之间比赛的情况，也可以用图表示出来。已知A队和其它各他队都比赛过一次，B队和A队比赛过，C队和B、D队比赛过，D队和C、E队比赛过，E队和A、C队比赛过。为了反映这个情况，可以用点分别代表这五个队，若两个队之间比赛过，就在这两队相应的点之间联一条线，这条线不过其它的点，如图所示。54321,,,,vvvvv1vv2v3v4v5例2：某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映这个情况要以点v1、v2、…、v8分别代表这八种药品，若药品vi和vj不能存放在同一个库房，则在vi和vj之间联一条线。问最少设几处库房才能安全存放这些药品。1vv2v3v4v7v8v5v686537421,,,,,,,vvvvvvvv§6.1图与网络的基本概念图论中图是由点和边构成，可以反映一些对象之间的关系。如物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连接起来的图进行模拟。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图2a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。图（Graph）由点（Vertex）和点之间的连线所构成的集合。不带箭头的连线称为边；带前头的连线称为弧。点和边的集合称为无向图（Undirectedgraph），如图(a)，用G={V，E}表示；点和弧的集合称为有向图（Directedgraph），如图(b)，用D={V，A}表示。1v4v2v3v1e2e3e4e5e6e7e8e3v1v2v4v5v6v1a2a5e3a4a6a7a8a(a)(b)■链（Chain）前后相继并且方向不一定相同的边序列称为链C={(1,2),(3,2),(3,4)}4231■回路（Circuit）起点和终点重合的路径称为回路μ={(1,2),(2,4),(4,1)}回路中各条边方向相同4231■路径（Path）前后相继并且方向相同的边序列P={(1,2),(2,3),(3,4)}■圈(Cycle)起点和终点重合的链称为圈ρ={(1,2),(2,4),(3,4),(1,3)}圈中各条边方向不一定相同4231■连通图任意两个节点之间至少有一条链的图称为连通图24351■树(Tree)无圈的连通图称为树树中只与一条边关联的节点称为悬挂节点1v2v3v5v4v6v7v8v9v10v3v1v2v5v4v6v7v赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。),(EVGEVG,VVEEGG给了一个图，如果图，使及，则称是的一个支撑子图。1vv2v3v4v7v8v5v61vv2v3v4v7v8v61vv2v3v4v7v8v6v5v8v2v3v4v5v6v7v1v8v2v4v5v7v8v5要求有连线的药品不能放在一起，只要找出一个点的序列，使放在一起的点互不相邻。13624758{,,},{,,},{},{}vvvvvvvv§6.2最短路问题最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。最短路问题是重要的最优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等等，而且经常被作为一个基本工具，用于解决其它的优化问题。1.给起点v1以标号(0,s)，表示从v1到v1的距离为02.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算sij=li+cij。在所有的sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。,,ijijvvvIvJ求解最短路的Dijkstra算法(双标号法）解：采用Dijkstra算法，可解得最短路径为v1v3v4v6各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4例1求下图中v1到v6的最短路练习：电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。V1（甲地）1517624431065v2V7（乙地）v3v4v5v6(22,6)V7（乙地）（0,s）V1（甲地）1517624431065(13,3)v2V5(14,3)V6(16,5)V3(10,1)V4(18,5)最终解得：最短路径v1v3v5v6v7，每点的标号见下图例3设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用5681118将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)12453570.250.80.350.50.30.60.90.10.40.251、某人每天从住处1开车至工作地7上班，由于每天早上他总习惯于处理很多事务，所以上班路上经常超速开车，这样就要受到交警的阻拦和罚款，图中各弧旁边的数字为开车上班时在各路线碰不到交警的可能性。试问该人应选择一条什么路线，使从家出发至工作地路上碰到交警的可能性最小？习题v1v8v7v6v5v4v3v2v11v10v964324257223255413654282、用标号法求v1到各点的最短距离0322261735441SACEBDFT网络各点之间最短路的矩阵算法ijdijd设为图中相邻两点的距离，若i点与j点不相邻时，令则有邻接矩阵：0SSSASBSCSDSESFSTASAAABACADAEAFATBSBABBBCBDBEBFBTCSCACBCCCDCECFCTDSDADBDCDDDEDFDTESEAEBECEDEEEFETFSFAFBFCFDFEFFFTTSTATBTCTDTETFTTddddddddddddddddddddddddddddddddDdddddddddddddddddddddddddddddddd02120224203120434340713057506160D0为对称矩阵(1)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)min{,,,,,,,}SBSSSBSAABSBBBSCCBSDDBSEEBSFFBSTTBddddddddddddddddd因为从i到j的最短路不一定是ij，可能是ilj，ilkj。先考虑ij之间有一个中间点的情况。(1)02446162022431134204371424043864340774133705116117875063141160D一般地有：(1)(0)(0)min{}ijirrjddd再构造由两个中间点的矩阵：(2)(1)(1)min{}ijirrjdddk个中间点的矩阵：()(1)(1)min{}kkkijirrjddd一般不超过()kDlg(1)1lg2pkk式中p为网络图中的节点数(2)0244616520224383420435714240438564340774135370566878750653154660D本例中计算到(2)D即得到最短路矩阵(3)D(2)D思考：假定上图各点代表8个村子，决定联合办一所小学，已知各村的小学生人数分别为S=30,A=40,B=25,C=20,D=50,E=60,F=55,T=60问小学应建在那个村子，使小学生上学走的总路程为最短。再计算则有§6.3最小生成树问题树是图论中的重要概念，所谓树就是一个无圈的连通图。管理组织机构图、决策树图、聚类分析的“龙骨图”、磁盘文件存放路径图、家族族谱图、经济管理中的因果分析图（鱼刺图）等等，因其与大自然中的树的特征相似而得名。上图中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，