运筹学图与网络分析

第5章图论与网络分析图的基本概念网络分析最小支撑树问题最短路径问题网络最大流问题ABCDACBD图论起源：哥尼斯堡七桥问题问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？结论：每个结点关联的边数均为偶数§1图的基本概念由点和边组成，记作G=(V，E)，其中V=(v1，v2，……，vn)为结点的集合，E=(e1，e2，……，em)为边的集合。点表示研究对象边表示研究对象之间的特定关系1.图p114图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：哥尼斯堡桥问题的图为一个无向图。有向图的边称为弧。例2：五个球队的比赛情况，v1v2表示v1胜v2。v1v2v3v4v52、图的分类v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例654321,,,,,vvvvvvV},,,,,,,,{10987654321eeeeeeeeeeE，],[211vve],[212vve],[323vve],[434vve],[315vve],[536vve],[537vve],[658vve],[669vve],[6110vve图1v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}图2v1v2v3v4v53、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：链与路中的点均不相同，则称为初等链(路)类似可定义初等圈（回路）4、连通图任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。G1G2G1为不连通图，G2为连通图例：5、支撑子图图G=(V，E)和G'=(V'，E')，若V=V'且E'E，则称G'为G的支撑子图。G2为G1的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2例：G2是G1的子图；v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)v1v2v3v4v5v6v7e1e6e7e9e10e11(c)例：6、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例：§2最小支撑树问题本节主要内容：树支撑树最小支撑树[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531树：无圈的连通图，记为T。一、树的概念与性质树的性质：（1）树的任2点间有且仅有1链；（2）在树中任去掉1边，则不连通；故树是使图保持连通且具有最少边数的一种图形（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有m个顶点，则T有m-1条边。(A)(B)(C)若一个图G=（V,E）的支撑子图T=（V,E´）构成树，则称T为G的支撑树，又称生成树。二、图的支撑树(G)(G1)(G2)(G3)(G4)例[例]某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？解：该问题实为求图的支撑树问题，共需铺4条路。v1v2v3v4v5图的支撑树的应用举例v1v2v3v4v555.53.57.5423用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8最小支撑树：求网络的支撑树，使其权和最小。三、最小支撑树问题算法1（破圈法）：①在给定的赋权的连通图上找一个圈；②在所找的圈中去掉一条权数最大的边(若有两条或两条以上的边都是权数最大的边，则任意去掉其中一条)：③若所余下的图已不含圈，则计算结束，所余下的图即为最小支撑树，否则，返问①。55.5v1v2v3v4v53.57.5423[例]求上例中的最小支撑树解：55.5v1v2v3v4v53.57.542355.5v1v2v3v4v53.57.54233v12v4v545v23.5v3算法2（避圈法）：从某一点开始，把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。最小生成树举例：某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v66515723445v1v4v5v6v2v31234v1v2v3v4v514231352[联系]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531[练习]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222452634531[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222252634531[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222222634531[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IABCDEFGHJKS222222234531[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为25万元§3最短路径问题最短路问题是在一个网络（赋权有向图）中寻找从起点到某个节点之间一条最短的路线。现欲求出υ1至υ6距离最短的路径。υ1υ2υ3υ4υ6υ5250300200400275150100150100基本思想：从起点vs开始，逐步给每个结点vj标号[dj,vi]，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点.若给终点vt标上号[dt,vi],表示已求出v1至vt的最短路其最短路长为dt，最短路径可根据标号vi反向追踪而得最短路问题的Dijstra解法（狄克拉斯）v2v1v3v4v5v6v7v8v9163222266133101044例题：求网络中v1到v9的最短路10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](3)考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。(1)给起点v1标号[0,v1](2)把顶点集V分成VA:已标号点集VB：未标号点集10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](3)考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。(1)给起点v1标号[0,v1](2)把顶点集V分成VA:已标号点集VB：未标号点集[3,v1][0,v1][1,v1][3,v1][5,v3]10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2]10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5]10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5]10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]此时终点v9已标号[12,v5]，则12即为v1→vn的最短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]v1到v9的最短路为：v1→v3→v2→v5→v9，最短距离为1210v2v1v3v4v5v6v7v8v91632222661331044p1195V5V24541V612455V4V1V8238V7V37练习：用Dijkstra算法求下图中V1至V8的最短路及最短路长。关键线路：1.V1--V2--V4--V6--V82.V1--V2--V4—V7--V8最短路长：12V35V5V24541V612455V4V1V8238V77(0,V1)(1,V1)(2,V1)(6,V2)(5,V2)(9,V4)(7,V4)(12,V6/V7)[课堂练习]无向图情形求网络中v1至v7的最短路。v1v2v3v4v5v6v7225355715713[课堂练习]无向图情形v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6][课堂练习]无向图情形答案（2）：v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]最短路模型的应用——设备更新问题第i年12345价格ai1111121213使用寿命0~11~22~33~44~5费用bj5681118例某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。最短路模型的应用——设备更新问题分析：结点：V={v1，…，v6}，vi表示第i年初；弧：A={(vi，vj)}表示第i年初购买，用至第j年初；i=1,…,5;j=2,…,6权cij：i年初~j年初的费用，即cij=i年初购买费+（j-i）年里的维修费通路：表示一个更新策略。例如v1-v2-v6表示第一年购买用到第二年更新，继续用至第五年末的一个更新策略最短路模型的应用——设备更新问题v2v1