指导chap7图论与网络优化模型

1、第七章 图论与网络优化模型 7.1 图论基本概念与最小生成树7.2 最短路问题7.3 网络最大流7.4 二分图与锁具装箱问题y实际背景 例1（公路连接问题）某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么如何决定在哪些城市间修建高速公路总成本最小？例2（最短路问题）一名货车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货车的运行速度是恒定的，那么这个问题相当于需要找到一条从甲地到乙地的

2、最短路。例3（运输问题）某种原材料有m个产地，现在需要将原材料从产地运往n个使用工厂。假定m个产地的产量和n个工厂的需求量已知，单位产品从任一产地到任一工厂的运费已知，那么，如何安排运输方案可以使总运输成本最低？实际背景 例4（指派问题）一家公司经理准备安排n名员工去完成n项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的收益不同，如何分配工作方案使总回报最大？例5（中国邮递员问题）一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线？即从邮局出发，经过投递区内每条街道至少一次，最后返回邮局。例6（旅行商问题）一名推销员准备前往若干城市推销产品。如何为他设

3、计一条最短的旅行路线？即从驻地出发，经过每个城市恰好一次，最后返回驻地。实际背景 共同特点：（1）它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为优化问题。（2）它们都易于用图形的形式直观的描述和表达，数学上把这种与图相关的结构称为网络，与图和网络相关的优化问题称为网络优化。哥尼斯堡七桥问题 在无孤立结点的图g中,若存在一条回路,它经过图中每条边一次且仅一次,称此回路为欧拉回路. 无向图g具有欧拉回路,当且仅当g是连通的,且所有结点的度都是偶数.图论基本概念与最小生成树一、 图 的 概 念1、图的定义2、顶点的次数 3、子图二、 图 的 矩 阵 表 示

4、1、 关联矩阵2、 邻接矩阵三、 最 小 生 成 树定义有序二元组g=(v,e )称为一个图.1 是有穷非空集，称为顶点集 其中的元素叫图g的顶点。2 e称为边集，其中的元素称为图g的边。 例设g=(v,e),其中g的图解如图12,nvv vv123412345,vv v v vee e e e e定义定义在图 g 中，与 v 中的有序偶(vi， vj)对应的边 e，称为图的有有向向边边（或弧） ，而与 v 中顶点的无序偶 vivj相对应的边 e，称为图的无无向向边边.每一条边都是无向边的图，叫无无向向图图；每一条边都是有向边的图，称为有有向向图图；既有无向边又有有向边的图称为混混合合图图.定

5、义定义若将图 g 的每一条边 e 都对应一个实数 w(e)，称 w(e)为边的权权，并称图 g 为赋赋权权图图.规定用记号和分别表示图的顶点数和边数.关联矩阵对无向图，其关联矩阵)(ijm，其中：不关联与若相关联与若jijiijevevm01m=43215432110110011000101110001vvvveeeee对有向图，其关联矩阵)(ijm，其中：不关联与若的终点是若的起点是若jijijiijevevevm011注：假设图为简单图邻接矩阵对无向图，其邻接矩阵)(ijaa，其中：不相邻与若相邻与若jijiijvvvva01注：假设图为简单图a=432143210111101011011

6、010vvvvvvvv对有向图（，） ，其邻接矩阵)(ijaa，其中：evvevvajijiij），若（），若（01对有向赋权图，其邻接矩阵)(ijaa，其中：evvjiwevvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义a=4321432105375083802720vvvvvvvv树的等价定义树的等价定义无回路的连通图无回路的连通图.无回路且无回路且=v-1 其中其中是是t的边数的边数,v是是t的结点数的结点数.连通的且连通的且=v-1.无回路但添加一条新边则得到一条仅有的回路无回路但添加一条新边则得到一条仅有的回路.连通的连通的,但删去任一条边但删

7、去任一条边,t便不连通便不连通.每对结点之间有一条且仅有一条路每对结点之间有一条且仅有一条路. 如果图如果图g的生成子图是树的生成子图是树, 则称此树为则称此树为g的的生成树生成树.例：某地要建例：某地要建5个工厂，拟修筑道路连接这个工厂，拟修筑道路连接这5处。经勘测处。经勘测其道路可依下图的无向边铺设。为使这其道路可依下图的无向边铺设。为使这5处都有道路处都有道路相通，问至少要铺设几条路？怎样铺设？相通，问至少要铺设几条路？怎样铺设？v1v4v5v2v3v1v4v5v2v3v1v4v5v2v3最小生成树（最小生成树（kruskal（克鲁斯克尔）算法）（克鲁斯克尔）算法） 设图设图g有有n个结

8、点，以下算法产生的是最小生成树个结点，以下算法产生的是最小生成树1）选取最小权边）选取最小权边e1，置边数，置边数i1；2）i=n-1结束，否则转入结束，否则转入3）；）；3）设已选择边为）设已选择边为e1,e2,ei, 在在g中选取不同于中选取不同于e1,e2,ei的边的边ei+1，使，使e1,e2,ei,ei+1中无回路且中无回路且ei+1是满足此条件的最小边；是满足此条件的最小边；4） ii1,转入转入2）。）。注意：最小生成树不唯一，但不同的最小生成树的边权之和是唯一的边按升序排序边按升序排序:边边(vi, vj)记成记成eij边权边权e28e34e23e38e17e24e45e57e

9、16e78e56e35e46e67e58e12e181 1 2 2 2 3 3 3 4 4 4 5 6 6 7 7 8v1 v5 v4v2 v3v8 v6v7 12213772486653443v1 v5 v4v2 v3v8 v6v7 1212433 to mtlb(kruskl.m)验证：p95例11最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路基 本 概 念通路44112544141vevevevevwvv道路4332264521141vevevevevevtvv路径4521141vevevpvv定义定义（）任意两点均有路径的图称为连通图连通图（）起点与终点重合

10、的路径称为圈圈（）连通而无圈的图称为树树定定义义（）设 p(u,v)是赋权图 g 中从 u 到 v的路径， 则称)()()(peeewpw为路径 p 的权权(2) 在赋权图 g 中，从顶点 u 到顶点 v的具有最小权的路 ),(*vup，称为 u 到 v的最最短短路路固定起点的最短路最短路是一条路径 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路dijkstra 算法算法：求 g 中从顶点 u0到其余顶点的最短路设 g 为赋权有向图或无向图，g 边上的权均非负对每个顶点，定义两个标记（l v( )

11、，z v( )） ，其中: l v( )：表从顶点 u0到 v 的一条路的权 z v( )：v 的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终l v( )为从顶点u0到 v 的最短路的权s：具有永久标号的顶点集输入: g 的带权邻接矩阵),(vuw算法步骤：（3） 设v*是使l v( )取最小值的s中的顶点，则令 s=sv*， uv*（4） 若s ，转 2，否则，停止.（2）更新l v( )、z v( )： vsvs,若l v( )l uw u v( )( , ) 则令l v( )=l uw u v( )( , ),z v( )= u例例 求下图从顶点 u1到其余顶

12、点的最短路先写出带权邻接矩阵： 03064093021509701608120w因 g 是无向图，故 w是对称阵 to mtlb(dijkstr.m)(iul迭代次数1u2u3u 4u5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12 12最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u)(iul1u2u3u 4u5u6u 7u 8u最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8验证

13、：p97例1每对顶点之间的最短路1、求距离矩阵的方法2、求路径矩阵的方法3、查找最短路路径的方法（一）算法的基本思想（二）算法原理（三）算法步骤算法的基本思想 直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵 d(1)、 d(2)、 、d()，使最后得到的矩阵 d()成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径算法原理 求距离矩阵的方法把带权邻接矩阵 w 作为距离矩阵的初值，即 d(0)=)()0(ijd=w（）d(1)= )() 1 (ijd，其中)0(1)0() 1 (,miniijijddd)0(1jd)1(ijd是从 vi到 vj的只允许以 v1作为中间点的路

14、径中最短路的长度（2）d(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是从 vi到 vj的只允许以 v1 、 v2作为中间点的路径中最短路的长度（）d()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是从 vi到 vj的只允许以 v1、v2、v作为中间点的路径中最短路的长度即是从 vi到 vj中间可插入任何顶点的路径中最短路的长，因此d()即是距离矩阵算法原理 求路径矩阵的方法r=)(ijr, rij的含义是从 vi到 vj的最短路要经过点号为 rij的点)()0()0(ijrr, jri

15、j)0(每求得一个 d(k)时，按下列方式产生相应的新的 r(k)否则若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距离矩阵的同时可建立路径矩阵r 即当vk被插入任何两点间的最短路径时，被记录在r(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径)(d)(r)(rij算法原理查找最短路路径的方法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.然后用同样的方法再分头查找若：（） 向点 i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向点 j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1

16、p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21, 12算法步骤floyd 算法：算法：求任意两点间的最短路d(i,j)：i 到 j 的距离r(i,j)：i 到 j 之间的插入点输入: 带权邻接矩阵 w(i,j)（） 赋初值：对所有 i,j, d(i,j)w(i,j), r(i,j)j, k1(2) 更新 d(i,j), r(i,j)对所有 i,j，若 d(i,k)+d(k,j)d(i,j)，则 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否则 kk+1，转（） 例、求下图任意两点之间的最短路径的长度654321654321654321

17、654321654321654321r,022203230142221034301210d例例 求下图中加权图的任意两点间的距离与路径 to mtlb(rod2(floyd)5333434331543243332344441,0646960243420256420793570rd951d，故从 v5到 v1的最短路为51r由 v4向 v5追朔：3, 35354rr;由 v4向 v1追朔：141r所以从 v5到 v1的最短路径为：1435.可化为最短路问题的多阶段决策问题最短路的应用（2）弧集 e=(,)v vij，i=1,2,3,4,5; ij6,弧(,)v vij表第 i 年初购进一台设备一

18、直使用到第 j 年初的决策，其权 w(,)v vij表由这一决策在第 i 年初到第 j 年初的总费用，如w(,)v v14=11+5+6+8=30.（2） 计算在各点iv设立服务设施的最大服务距离)(ivs max)(1ijjidvs , 2 , 1i 选址问题-中心问题例例 2某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在那个区，才能使它至最远区的路径最短（1）用 floyd 算法求出距离矩阵 d=)(ijd（3）求出顶点kv，使)(min)(1iikvsvs则kv就是要求的建立消防站的地点此点称为图的中心点中心点 to mtlb(rod3(floyd)05 .15 .55

19、 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530ds(v1)=10, s(v2)=7, s(v3)=6, s(v4)=8.5, s(v5)=7, s(v6)=7, s(v7)=8.5s(v3)=6,故应将消防站设在v3处。 7.3 7.3 网络流问题网络流问题 1、 网络流图2 、最大流问题及其解法3 、最小费用问题及其解法问题1：7种设备要用5架飞机运往目的地，每种设备各有4台，这5架飞机的容量分别为8，8，5，4，4台，问能否有一种装载法，使同一种类型的设备不会有两台在同一架飞机上。问

20、题2：设有王二、张三、李四、赵五四人及小提琴、大提琴、钢琴和吉他四种乐器，已知四人的特长如下： 王二擅长拉大提琴和弹钢琴； 张三擅长拉小提琴、大提琴和吉他； 李四擅长拉小提琴和大提琴； 赵五只会弹吉他；今假设四人同台演出，每人奏一种乐器，问四人同时各演奏一种乐器时所有可能的方案。网络流图是满足下列条件的有向赋权图网络流图是满足下列条件的有向赋权图),(wevg （1 1）有一个发点）有一个发点 和收点和收点（2 2）每条边都有一个容量（权）每条边都有一个容量（权）ss),(jivvw 实际含义是发点可以看作运输问题的起点，收点可以看作运实际含义是发点可以看作运输问题的起点，收点可以看作运输问题

21、的终点，边可以看作运输路线，权数可以看作该线路的输问题的终点，边可以看作运输路线，权数可以看作该线路的运输能力。运输能力。 设设 是定义在有向赋权图是定义在有向赋权图 边集边集 上的上的一个数值函数，满足：一个数值函数，满足：),(jivvf),(wevg e（2）除过发点和起点外，),(),( , ),(),(xvvyvyfxvfiiyixi和的边。和离开分别是进入iivv),(),(jijivvwvvf（1 1）一、网络流图的流。是则称),(),(. 0),(),(wevgvvfqysfsxfjiyx该定义的实际意义分别为：1、每条边的实际流量不超过它的容量。2、流入和流出每个节点的流量相

22、等。（物质不灭，无损耗）3、从发点流出的流量等于流入收点的流量。称 的流值。为流)(),(),()(,jiyxvvfsyfxsffq3、二、最大流问题及其求解方法 （一）最大流问题最大流问题 设有向网络n（v，），在发点vs 有一批货，要通过网络上的弧运输到收点vt 去，受运输条件限制，每条弧ij在单位时间内通过的车辆数不能超过cij 辆，分析：如何组织运输才能使从vs到vt 在单位时间内通过的车辆达到最多？ 上面描述的这类问题，称为最大流问题。 最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问题上。例：如图1中，有一批物资需要用汽车尽快从发点运到

23、收点，弧（i，j）上所标的数字表示该条道路在单位时间内最多能通过的车辆数（单位：百辆），问如何调运，才能使单位时间里有最多的车辆从调到。425136756385577113223图1 点出发的车辆数应该与点到达的车辆数相同，除和以外的各中间点，进的车辆数应该与离去的车辆数应该相同。fxxxxx67571413126765564636575665352546341436353432231325233212xxxxxxxxxxxxxxxxxxxxxxxxij 是通过弧(i，j)的车辆数。（1）（4）（5）（6）（2）（3） 对所有弧（i，j），应满足约束 满足（1）（7）的解称为从到的一个可行流，

24、 我们的目的：在所有可行流中求出一个方案，使得这个可行流得到的 f 最大。 若从收点到发点连接一条假想弧(7，1)，设它的容量c71=，那么 对点： 对点： 最大流问题的目标为 ijijcx 0（7）14131271xxxx716757xxx（8）（9）（10）max71x所以，对于发点为vs，收点为vt的网络n（v，u），当增加一条约束为cts=的假想弧（t，s）后，最大流问题就成为： 容量约束： 平衡条件： 目标函数： ijijcx 0ujjijuijjixx),(),(maxstx（11）（12）（13）（二）求最大流的方法：弧标号法 尽管最大流问题可以用线性规划模型描述，但是我们一般并

25、不用求解线性规划的方法求最大流，而是用一种更为简便明了的图上作业法弧标号法，求解上述最大流问题。 为了便于弧标号法的计算，首先需要将最大流问题（譬如图1）重新改画成为图2的形式。 2416357st650230081023730071000055图2 在图在图2 2中，每条弧中，每条弧 上标有两个数字，其中，上标有两个数字，其中，靠近点靠近点 i 的是的是 ，靠近点，靠近点 j j 的是的是 。如。如 表示从表示从到到的最大通过量是的最大通过量是5 5（百辆），从（百辆），从到到的最大通过量是的最大通过量是0 0； 表示从表示从到到和从和从到到都可以通过都可以通过2 2（百辆）；等等。（百辆）

26、；等等。 ijcjic05222416357st650230081023730071000055ijv图2 求最大流的基本步骤： 弧标号法求最大流的过程，就是对图2反复地进行修改的过程，其计算步骤如下： 步骤1. 从发点s到收点t选定一条路，使这条路通过的所有弧vij的前面约束量cij都大于0，如果找不到这样的路，说明已经求得最大流，转步骤4。 步骤2. 在选定的路上，找到最小的容许量cij定为p。 步骤3. 对选定的路上每条弧的容量作以下修改，对于与路同向的弧，将cij修改为cij-p，对于与路反向的弧，将cij修改为cij+p。修改完毕后再转入步骤1。步骤4.用原图中各条弧上起点与终点数值

27、减去修改后的图中对应点的数值，得到正负号相反的两个数，并将从正到负的方向用箭头表示。这样，就得到一个最大流量图。 下面，我们用弧标号法求解图2中的最大流。 第一次修改第一次修改：（1）从发点）从发点s到收点到收点t找一条路，使得这条路上的找一条路，使得这条路上的所有弧前面的约束量所有弧前面的约束量 。从图。从图2 2中可以看出，中可以看出，显然，显然，就是满足这样的条件的一就是满足这样的条件的一条路。条路。 （2）在路中, , , ,所以取 。 0ijc613c736c767c613 cp（3）在路中，修改每一条弧的容量： 066613-pc660031pc660063pc16-7767pc1

28、6-7736pc660076pc通过第1次修改，得到图3。 2416357st05023008162 3130611600055图3返回步骤（1），进行第2次修改。 第二次修改：选定，在这条路中，由于 ，所以，将 改为2 ， 改为0， 改为5， 、 、 改为3。修改后的图变为图4。 325 cp12c25c57c21c52c75c2416357st023203051623133611600055返回步骤（1），继续做第3次修改。 图4第三次修改：取，在这条，由于 ，所以将 改为0， 改为5， 改为0， 改为4， 改为1， 改为2， 改为3， 改为5。修改后的图变为图5。 12c21c23c32

29、c35c53c57c75c2cp122416357st005003231641135611600055图5返回步骤（1），继续做第4次修改。 第四次修改：选定，在这条路中，由于 p =c67 =1，所以将c14改为4,c41改为1,c46改为4,c64改为1,c67改为0，c76 改为7。修改后的图为变为图6 。 2416357st00500323164 1135701611044图6返回步骤（1），继续做第5次修改。 第五次修改：选定,在这条路中，由于 p = c65 = 1，所以将c14和c46均改为3，c65改为0，c57改为2，c41、c64、c56均改为2，c75改为6。修改后的图变

30、为图7。 2416357st005003222641136500622033图7 需要注意的是，由图7中可以看出，弧 本来在图2中是无容量可通过的，但经过几次修改，由 变成 ，即此时从到还可通过1（百辆），而从到，可以通过6（百辆）的容量，这说明，修改过程实际上是把计划中从到的通过车辆数减少了。0761(6,3)取，在这条路中，由于p=c35=1，所以将 c14和 c46均改为2，c63改为5, c35改为0，c57改为1，c41、c64、c53均改为3，c36改为2，c75改为7。修改后的图变为图8。 2416357st005003312640237500533022图8 在图8中，从发点到

31、收点，再也不存在连通的起点容量都大于零的弧了，所以图8为最大流图。 转入步骤（4），用原图中各条弧上起点与终点数值减去修改后的图上各点的数值，将得到正负号相反的两个数，将这个数标在弧上，并将从正到负的方向用箭头表示,这样就得到最大流量图。例如原来弧 是 ，现在是 ，相减为5，那边为正，我们就记作 。这样，就得到图9，即最大流量。依这样的调度方式，可以从发点s调运14（百辆）汽车到收点t。 07525(3,6)6373371035542513672图9 最大流量图 图10最大流fmx的大小是确定的，但最大流的路线可以不唯一。在上例中，如果从不同的路开始来修改图，也可能得到另外一个最大流图（图10）。 2416357563233177235注意验证：p104 例2应用举例 一制造商需要把两个车间d1,d2生产的同类商品通过运输网络送到三个销售点m1,m2,m3去，如图所示。设各销售点计划销售量分别为10,8,8，问网络的运输能力能否满足这一要求？两个车间生产数量多少最为恰当？三、 最小费用