运筹学图论课件

第五章图与网络分析§1图与网络的基本概念

§2最小生成树问题

§3最短路问题

§4最大流问题

运筹学图论5-1图与网络的基本概念运筹学图论一、图与网络的基本概念1、图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图7-1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图7-1运筹学图论

当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图5-2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图5-2运筹学图论a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图5-3

如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图5-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。运筹学图论2、无向图：由点和边构成的图，记作G=（V，E）。3、有向图：由点和弧构成的图，记作D=（V，A）。4、连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。5、回路：若路的第一个点和最后一个点相同，则该路为回路。6、赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。7、网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。运筹学图论二、七桥问题ACBD哥尼斯堡的普雷格尔河运筹学图论提出问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。1973年，欧拉将此问题归结为如图所示的一笔画问题。

·

·

·

·ACBDd(A)=3d(B)=3d(C)=5d(D)=3运筹学图论将点看成事物，边看成事物与事物的联系。秩为奇数的为奇顶点；秩为偶数的为偶顶点。如何一个图都可以由边的集合和点的集合所组成。点——不考虑位置；边——不考虑形状与联系；欧拉定理：

a、一个图奇顶点的个数为“0”时，可既不重复，也不遗漏走完所有桥还能回到原处。

b、一个图奇顶点的个数为“2”时，可不重复，不遗漏走完所有桥但不能回到原处；

c、一个图奇顶点的个数大于“2”时，不可能既不重复，也不遗漏走完而且回到原处。运筹学图论案例1：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如表所示中打的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√ABCDEF●●●●●●A-C-B-F-E-D运筹学图论ABCDEF●●●●●●A-E-B-C-D-FA-E-C-B-D-F案例2：某厂办公室在三天内开一个会，请10位领导第一天上午开幕式A第三天下午闭幕式F每天每位领导只能开半天会。

领导内容12345678910A√√√√√√B√√√√C√√√√√D√√√E√√√F√√√√√运筹学图论5-2最小生成树问题运筹学图论树是图论中的重要概念，所谓树就是一个无圈的连通图。

图7-4中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图7-4v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)运筹学图论

给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图7-5中，(b)和(c)都是(a)的生成子图。如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图7-5中，(c)就是(a)的生成树。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。图7-5(a)(b)(c)运筹学图论一、求解最小生成树的破圈算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。运筹学图论e3e7V1V3V2V4V5V6e1e6e8e251e452e5734e94例1：如何架设电话线，使得耗材最少？5（一）破圈法：丢边（大边），破圈。∴最少费用为：5+1+2+3+4=15运筹学图论e3e7V1V3V2V4V5V6e6e8e251e452e5734e94例2：如何架设电话线，使得耗材最少？e15（二）避圈法：∴最少费用为：5+1+2+3+4=15运筹学图论练习：（a）3213232252534222破圈法：最小支撑树=18运筹学图论3213232252534222避圈法：最小支撑树=18运筹学图论（b）7538623554破圈法：最小支撑树=22运筹学图论（b）7538623554避圈法：最小支撑树=22运筹学图论5-3最短路问题运筹学图论最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs

到Vt

的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。一、Dijkstra算法1、思路：这种算法的基本思路是：假定V1-V2-V3-V4是V1-V4的最短路。2、假设：若用dij表示两相邻点i与j的距离，若i与j不相邻，令dij=∞，显然dii=0。3、步骤：（1）从点s出发，因Lss=0，将此值标注在s旁的小方框内，表示s点已标号；（2）从s点出发，找出与s相邻的点中距离最小的一个，设为r。将Lsr=Lss+dsr的值标注在r旁的小方框内，表明点r已标号；（3）从已标号的点出发，找出与这些点相邻的所有未标号点p。若有Lsp=min{Lss+dsp；Lsr+drp}，则对p点标号，并将Lsp的值标注在p点旁的小方框内；（4）重复第3步，一直到t点得到标号为止；运筹学图论例1、从发电厂向某城市输送电，必须通过中转站转送，如下图，电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。1642534323322解：L1r=min{d12,d13}=min{4，3}=3=L13L1p=min{L11+d12，L13+d35}=min{0+4，3+3}=4=L12L1p=min{L12+d24，L12+d25，L13+d35}=min{4+3，4+2，3+3}=6=L15L1p=min{L12+d24，L15+d56}=min{4+3，6+2}=7=L14L1p=min{L14+d46，L15+d56}=min{7+2，6+2}=8=L16所以：最短路是V1V3V5V6

路长是P（6）=8运筹学图论例2：求下图中V1到V6的最短路1563423253725115解：L1r=min{d12,d14，d13}=min{3，5，2}=2=d13L1p=min{L11+d12，L11+d14，L13+d34}=min{3，5，3}=3=L12=L14L1p=min{L12+d26，L14+d46}=min{3+7，3+5}=8=L16得到结果：从1—6最短路为1—3—4—6，5没有标号，说明从1—5没有有向路运筹学图论

例3求下图中v1到v6的最短路解：采用Dijkstra算法，可解得最短路径为v1v3v4v6

各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4运筹学图论

例4电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。

解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。V1（甲地）15176244431065v2V7（乙地）v3v4v5v6运筹学图论例4最终解得：最短路径v1v3v5v6v7，每点的标号见下图（0,s）

V1（甲地）1517624431065(13,3)v2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)运筹学图论二、矩阵算法：P1261、思路：这种算法的基本思路是：假定V1-V2-V3-V4是V1-V4的最短路。也是V4-V1的最短路。2、假设：若用dij表示两相邻点i与j的距离，若i与j不相邻，令dij=∞，显然dii=0。3、步骤：（1）从点s出发，因Lss=0，将此值标注在s旁的小方框内，表示s点已标号；（2）从s点出发，找出与s相关的所有点，设为r。将Lsr=Lst+dtr的值，从中选择min；为此可以构造出一个新的矩阵D（1）。则D（1）矩阵给出了网络中任意两点之间直接到达和包括经过一个中间点时的最短距离。（3）再构造矩阵D（2）。令dij(2)=min{dir(1)+drj(1)},则D（2）给出了网络中任意两点直接到达，及包括经过一个至三个中间点时的最短距离。（4）重复第1，2，3步，一直到出现D(m+1)=D(m)时为止。运筹学图论练习：某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。16754324187121626856(4,1)(16,2)(18,3)(22,3)(25,4)(27,5)运筹学图论

例6设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用5681118运筹学图论例6的解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186运筹学图论(继上页)把权数赋到图中，再用Dijkstra算法求最短路。

最终得到下图，可知，v1到v6的距离是53，最短路径有两条：

v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)运筹学图论5-4最大流问题运筹学图论最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型例6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图5-6运筹学图论

我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：运筹学图论

在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤cij。我们把满足守恒条件及流量可行条件的一组网络流{fij}称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。我们把例6的数据代入以上线性规划模型，用“管理运筹学软件”，马上得到以下的结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最优值（最大流量）=10。运筹学图论基本概念：容量：对网络上的每条弧都给予一个最大的通过能力，称为弧的容量。可行流：即满足最大流：从网络的发点到收点之间允许通过的最大流量。割：将容量网络中的发点和收点分割开，并使发点到收点的流中断的一组弧的集合。P130运筹学图论求网络最大流的标号算法步骤：P132例：P132运筹学图论4、求网络最大流，图中数据为Cij1055105155Vt1010252020205551010Vs运筹学图论P137.572426618434732135V1V2V5V3V4V8V7V6破圈法最小支撑树=16（a）运筹学图论P137.572426618434732135V1V2V5V3V4V8V7V6避圈法最小支撑树=16运筹学图论24236106158462182108121057V1V6V5V7V3V2V4V11V9V8V10破圈法：最小支撑树=32运筹学图论24236106158462182108121057V1V6V5V7V3V2V4V11V9V8V10避圈法：最小支撑树=32运筹学图论P137.813