图与网络模型的基本概念

第十一章图与网络模型§1图与网络的基本概念§2最短路问题§3最小生成树问题§4最大流问题§5最小费用最大流问题1§1图与网络的基本概念图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图11-12§1图与网络的基本概念

当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图11-2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图11-23§1图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。4§1图与网络的基本概念无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：

在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。5§2最短路问题最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。一、求解最短路的Dijkstra算法(双标号法）步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合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。6§2最短路问题例1求下图中v1到v6的最短路解：采用Dijkstra算法，可解得最短路径为v1v3v4v6各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v47§2最短路问题例2电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。V1（甲地）15176244431065v2V7（乙地）v3v4v5v68§2最短路问题例2最终解得：最短路径v1v3v5v6v7，每点的标号见下图（0,s）V1（甲地）1517624431065(13,3)v2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)9§2最短路问题例3设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用568111810§2最短短路问题例3的解：：将问题转化化为最短路路问题，如如下图：用vi表示“第i年年初购购进一台新新设备”,弧（vi,vj）表示第i年年初购购进的设备一直使使用到第j年年初。。把所有弧的的权数计算算如下表：：v1v2v3v4v5v612345611622304159216223041317233141723518611§2最短短路问题(继上页)把权数数赋到图中中，再用Dijkstra算算法求最短短路。最终得到下下图，可知知，v1到v6的距离是53，最短短路径有两两条：v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)12§3最小小生成树问问题树是图论中中的重要概概念，所谓谓树就是一一个无圈的的连通图。。图11-11中，(a)就是是一个树，，而(b)因为图中中有圈所以以就不是树树，(c)因为不不连通所以以也不是树树。图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)13§3最小小生成树问问题给了一个无无向图G=(V,E)，我们们保留G的的所有点，，而删掉部部分G的边边或者说保保留一部分分G的边，，所获得的的图G，称称之为G的的生成子图图。在图11-12中，(b)和(c)都是(a)的生生成子图。。如果图G的的一个生成成子图还是是一个树，，则称这个个生成子图图为生成树树，在图11-12中，(c)就是(a)的生生成树。最小生成树树问题就是是指在一个个赋权的连连通的无向向图G中找找出一个生生成树，并并使得这个个生成树的的所有边的的权数之和和为最小。。图11-12(a)(b)(c)14§3最最小小生生成成树树问问题题一、、求求解解最最小小生生成成树树的的破破圈圈算算法法算法法的的步步骤骤：：1、、在在给给定定的的赋赋权权的的连连通通图图上上任任找找一一个个圈圈。。2、、在在所所找找的的圈圈中中去去掉掉一一个个权权数数最最大大的的边边（（如如果果有有两两条条或或两两条条以以上上的的边边都都是是权权数数最最大大的的边边，，则则任任意意去去掉掉其其中中一一条条））。。3、、如如果果所所余余下下的的图图已已不不包包含含圈圈，，则则计计算算结结束束，，所所余余下下的的图图即即为为最最小小生生成成树树，，否否则则返返回回第第1步步。。15§3最最小小生生成成树树问问题题例4用用破破圈圈算算法法求求图图（（a））中中的的一一个个最最小小生生成成树树v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)图11-1316§3最小小生成树问问题例5、某大大学准备对对其所属的的7个学院院办公室计计算机联网网，这个网网络的可能能联通的途途径如下图图，图中v1,…,v7表示7个学学院办公室室，请设计计一个网络络能联通7个学院办办公室，并并使总的线线路长度为为最短。解：此问题题实际上是是求图11-14的的最小生成成树，这在在例4中已已经求得，，也即按照照图11-13的(f)设计计，可使此此网络的总总的线路长长度为最短短，为19百米。“管理运筹筹学软件””有专门的的子程序可可以解决最最小生成树树问题。v1331728541034v7v6v5v4v2v3图11-1417§4最大大流问题最大流问题题：给一个个带收发点点的网络，，其每条弧弧的赋权称称之为容量量，在不超超过每条弧弧的容量的的前提下，，求出从发发点到收点点的最大流流量。一、最大流流的数学模模型例6某某石油公司司拥有一个个管道网络络，使用这这个网络可可以把石油油从采地运运送到一些些销售点，，这个网络络的一部分分如下图所所示。由于于管道的直直径的变化化，它的各各段管道（（vi,vj）的流量cij（容量）也也是不一样样的。cij的单位为万万加仑/小小时。如果果使用这个个网络系统统从采地v1向销地v7运送石油，，问每小时时能运送多多少加仑石石油？v563522241263v1v2v7v4v3v6图11-2618§4最大大流问题我们可以为为此例题建建立线性规规划数学模模型：设弧(vi,vj)上流量为为fij，网络上的的总的流量量为F，则则有：19§4最大大流问题在这个线性性规划模型型中，其约约束条件中中的前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。。20§4最最大大流问问题二、最最大流流问题题网络络图论论的解解法对对网络络上弧弧的容容量的的表示示作改改进。。为省省去弧弧的方方向，，如下下图:(a)和(b)、(c)和(d)的意意义相相同。。用以上上方法法对例例6的的图的的容量量标号号作改改进，，得下下图vivjvivjcij0（a））（b））cijcijvivj（cji）（c））vivjcijcji（d））63522241263v1v2v5v7v4v3v60000000000021§4最最大大流问问题求最大大流的的基本本算法法（1））找出出一条条从发发点到到收点点的路路，在在这条条路上上的每每一条条弧顺顺流方方向的的容量量都大大于零零。如如果不不存在在这样样的路路，则则已经经求得得最大大流。。（2））找出出这条条路上上各条条弧的的最小小的顺顺流的的容量量pf，通过过这条条路增增加网网络的的流量量pf。（3））在这这条路路上，，减少少每一一条弧弧的顺顺流容容量pf，同时时增加加这些些弧的的逆流流容量量pf，返回回步骤骤（1）。。用此方方法对对例6求解解：第一次次迭代代：选选择路路为v1v4v7。弧（（v4,v7）的顺顺流容容量为为2，，决定了了pf=2，，改进进的网网络流流量图图如下下图：：63522241263v1v2v5v7v4v3v600000000000420222§4最最大大流问问题第二次次迭代代：选选择路路为v1v2v5v7。弧（（v2,v5）的顺顺流容容量为为3，决决定了了pf=3，，改进进的网网络流流量图图如下下图：：第三次次迭代代：选选择路路为v1v4v6v7。弧（（v4,v6）的顺顺流容容量为为1，决决定了了pf=1，，改进进的网网络流流量图图如下下图：：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v60000004202203333301323第四次次迭代代：选选择路路为v1v4v3v6v7。弧（（v3,v6）的顺顺流容容量为2，决决定了了pf=2，，改进进的网网络流流量图图如下下图：：第五次次迭代代：选选择路路为v1v2v3v5v7。弧（（v2,v3）的顺顺流容容量为2，决决定了了pf=2，，改进进的网网络流流量图图如下下图：：22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205§4最最大大流问问题24经过第第五次次迭代代后在在图中中已经经找不不到从从发点点到收收点的的一条条路，，路上上的每每一条条弧顺顺流容容量都都大于于零，，运算算停止止。得得到最最大流流量为为10。最大流流量图图如下下图：：22v1v2v5v7v4v3v6123522355§4最最大大流问问题“管理理运筹筹学软软件””中还还有专专门的的子程程序用用于解解决最最大流流问题题。25§5最最小小费用用最大大流问问题最小费费用最最大流流问题题：给给了一一个带带收发发点的的网络络，对对每一一条弧弧（vi,vj），除除了给给出容容量cij外，还还给出出了这这条弧弧的单单位流流量的的费用用bij，要求一个个最大大流F，并并使得得总运运送费费用最最小。。一、最最小费费用最最大流流的数数学模模型例7由由于输输油管管道的的长短短不一一，所所以在在例6中每每段管管道（（vi,vj）除了有不不同的的流量量限制制cij外，还还有不不同的的单位位流量量的费费用bij，cij的单位位为万万加仑/小时时，bij的单位位为百百元/万加加仑。。如图图。从从采地地v1向销地v7运送石油，怎样运送送才能运送最最多的石油并并使得总的运运送费用最小小？求出最大大流量和最小费用用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)26§5最小费费用最大流问问题这个最小费用用最大流问题题也是一个线线性规划的问问题。解：我们用线线性规划来求求解此题，可可以分两步走走。第一步，先求求出此网络图图中的最大流流量F，这已已在例6中建建立了线性规规划的模型，，通过管理运运筹学软件已已经获得结果果。第二步，在最最大流量F的的所有解中，，找出一个最最小费用的解解，我们来建建立第二步中中的线性规划划模型如下：：仍然设弧（vi,vj）上的流量为为fij，这时已知网网络中最大流流量为F，只只要在例6的的约束条件上上，再加上总总流量必须等等于F的约束束条件：f12=f14=F,即即得得此此线线性性规规划划的的约约束束条条件件，，此此线线性性规规划划的的目目标标函函数数显显然然是是求求其其流流量量的的最最小小费费用用。。由此此得得到到线线性性规规划划模模型型如如下下：：27§5最最小小费用用最大大流问问题28§5最最小小费用用最大大流问问题用管理理运筹筹学软软件，，可求求得如如下结结果：：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。。其最最优值值(最最小费费用)=145。对对照前前面例例6的的结果果，可可对最最小费费用最最大流流的概概念有有一个个深刻刻的理理解。。如果我我们把把例7的问问题改改为：：每小小时运运送6万加加仑的的石油油从采采地v1到销地地v7最小费费用是是多少少？应应怎样样运送送？这这就变变成了了一个个最小小费用用流的的问题题。一一般来来说，，所谓谓最小小费用用流的的问题题就是是：在在给定定了收收点和和发点点并对对每条条弧(vi,vj)赋权权以容容量cij及单位位费用用bij的网络络中，，求一一个给给定值值f的的流量量的最最小费费用，，这个个给定定值f的流流量应应小于于等于于最大大流量量F，，否则则无解解。求求最小小费用用流的的问题题的线线性规规划的的模型型只要要把最最小费费用最最大流流模型型中的的约束束条件件中的的发点点流量量F改改为f即可可。在在例6中只只要把把f12+f14=F改改为f12+f14=f=6得得到了了最小小费用用流的的线性性规划划的模模型了了。29§5最最小小费用用最大大流问问题二、最小费费用最大流流的网络图图论解法对网络上弧弧（vi,vj）的（cij,bij）的表示作作如下改动动，用(b)来表示示(a)。。用上述方法法对例7中中的图形进进行改进，，得图如下下页：vivjvivj（cij,bij）（0,-bij）（a）（b）（cij,bij）（cij,bij）vivj（cji,bji）（cij,bij）vivj（cji,bji）（0,-bji)（0,-bji)（c）（d）30§5最小小费用最大大流问题求最小费用用最大流的的基本算法法在对弧的标标号作了改改进的网络络图上求最最小费用最最大流的基基本算法与与求最大流的基基本算法完完全一样，，不同的只只是在步骤骤（1）中中要选择一一条总的单位费用最最小的路，，而不是包包含边数最最小的路。。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）图11-2831§5最小小费用最大大流问题用上述方法法对例7求求解：第一次迭代代：找到最最短路v1v4v6v7。第一次迭迭代后总总流量为为1，总总费用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图11-2932§5最最小费用用最大流流问题第二次迭迭代：找找到最短短路v1v4v7。第二次迭迭代后总总流量为为3，总总费用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图11-3033§5最最小费用用最大流流问题第三次迭迭代：找找到最短短路v1v4v3v6v7。第三次迭迭代后总总流量为为5，总费费用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(3,-4)（2,-3）图11-3134§5最最小费用用最大流流问题第四次迭迭代：找找到最短短路v1v4v3v5v7。第四次迭迭代后总总流量为为6，总费费用72。(6,6)(3,4)(4,7