第五章图论与网络模型

1、第五章图论与网络模型图论起源于 年Euler 对著名的K迸igsberg 七桥问题的讨论由于社会历史条件的限制，在此后的 多年里发展缓慢到 世纪中叶，由于对电网络、晶体模型和分子结构等的研究，图论又重新引起人们的重视尤其是 世纪中叶以来，随着数学对各个领域的广泛渗透和计算机的广泛应用，离散数学问题处于越来越重要的地位，图论作为一门提供离散数学模型和求解方法的应用数学学科，新的成果大量涌现由于图论具有能解决许多用传统数学方法无法解决的问题的特殊功能，以及形象和直观的特点，人们应用图论来解决交通运输、生产规划、经济管理、运筹学、系统论、控制论、信息论、数值分类、计算机科学、通信网络、开关电路、博奕

2、论、地理学、生物学、心理学等领域中的许多实际问题，图论成为一个引人注目的十分活跃的学科随着实践的发展，其巨大的潜力将会被人们进一步认识、发掘和利用本章介绍图论的一些基本概念与理论，典型问题和建立图论与网络模型的思路，以及常用的算法第一节基本概念现实世界的许多现象可用一类图形来描述，这种图形由一个点集和连接该点集中某些点对的边所构成例如，用点表示车站，边表示车站间道路的交通示意图；用点表示人，边表示一对朋友的人际关系图对这种图形，人们主要感兴趣的是有哪些点其两点之间能被一条边连接，而点的相对位置及边的长短曲直则无关紧要大量的这类事实的数学抽象，导致了图的概念序偶（V ，E）称为图，记作G （V

3、，E） ，其中顶点构成的集合V称为顶点集或点集，V 中的点对之间的边构成的集合E 称为边集V 称为图G 的阶G 的边可以无方向（称为无向边） ，也可以有方向（称为有向边或弧） ，记为e uv ，其中u ，v V ，e E ，称e 的两个端点u 与v 相邻，u ，v 与e 相互关联在有向边e uv 中，u ，v 分别称为e 的始点和终点有公共端点的两条边称为相邻边端点重合的边称为环同一对顶点间边的条数称为边的重数无环且无重数大于 的边的图称为简单图只有无向边的图称为无向图，只有有向边的图称为有向图，既含无向边又含有向边的图称为混合图图中与顶点v关联的边数称为v 的次数或度数，记为d（v） ；有向

4、图中以v 为始点（终点）的边数称为v 的出度（入度） ，记为d （v）（d （v） 显然d（v） d （v） d （v） 图的顶点的次数有如下性质： v Vd（v） E ； 图中次数为奇数的顶点必为偶数个； v Vd （v ） v Vd （v） 每个顶点的度为n 的n 阶无向图称为n 阶无向完全图，记为K n 每个顶点的出度和入度均为n 的n 阶有向图称为n 阶有向完全图，也记为K n 若G 的顶点集V 可分成两个不相交的非空子集V ，V ，使G 的每条边的端点，一个属于V ，另一个属于V ，则称G 为二分图或偶图，记为G （V ，V ，E） 若简单二分图G （V ，V ，E）中V 的每个顶点

5、与V 的所有顶点相邻，则称G为完全二分图，记为K n ，m ，其中n V ，m V 图论中的图与位置、大小、形状、面积、体积等几何要素无关，是一种更抽象的图图的最本质的内容实际上就是一个二元关系，即点与边的关联关系因此具有二元关系的系统或结构便可用图作为数学模型，且图具有直观性和艺术性，应用相当广泛设G （V ，E） ，G （V ，E） ，若V 彻V ，E 彻E ，则称G为G的子图特别地，若V V ，则称G为G 的生成子图；若V 彻V ，E含G 在V之间的所有边，则称G为由V导出的子图，记为GV ， 数学建模（本科册）GV V记为G V ；若E 彻E ，V含E中边的全体端点，则称G为由E导出的

6、子图，记为GE ；从G 中删去E的所有边得到的生成子图记为G E ，在G 上增加E的所有边得到的图记为G E G （V ，E）中的一个点边交替序列 v e v e v ek v k称为G 的一条通路（有向通路） ，简记为 v v v k ，其中ei的端点为v i 和v i （ei的始点为v i ，终点为v i ） ，i ， ， ，k ，k 称为 的长点均不同的通路（有向通路）称为链或路径（有向链或有向路径） 若v v k ，则通路（有向通路）称为回路（有向回路） ，链（有向链）称为圈（有向圈） 若无向图G 的任意两点间都存在通路，则称G 为连通图若V 分成非空子集V ，V ， ，V r ，当且

7、仅当u ，v V i时，u 与v 之间才有通路，则称子图GV ，GV ， ，GV r 为G 的连通分支连通分支的个数记为w（G） 对有向图G 的任意两点u 与v ：若存在从u 到v 及从v 到u 的通路，则称G 是强连通的；若存在从u 到v 或从v 到u 的通路，则称G 是单向连通的；若不考虑G 的边的方向，即G 作为无向图是连通的，则称G 是弱连通的设G 为无向图，V v ，v ， ，v n ，E e ，e ， ，em 若mij 表示v i与e j 关联的次数，则称M （m ij ） n m为G 的关联矩阵，M 表示G 的点与边的关联关系；若aij 表示边v i v j 的重数，则称A （a

8、ij ）n n为G 的邻接矩阵，A 表示G 的点与点的相邻关系若G 为无环有向图，令m ij ， e j v i v k E ， ， e j v k v i E ， ， 其他，则称M （mij ）n m为G 的关联矩阵，若aij 表示有向边v i v j 的重数，则称A （aij ）n n为G 的邻接矩阵图的矩阵化意味着更适于把图存储在计算机中和对图作数学运算，使人们可从矩阵代数的观点来研究图的性质，同时它也有很多实际应用例1 某房管所将管理的房屋分成 类，设各类房已住满，每年因各种原因有住户要求换房换房需求如下面的矩阵C （c ij ）所示，其中cij 表示第i 类房住户要求换到第j 类房的

9、需求量假设系统封闭，要求设计一个换房方案，最大限度满足住户需求C （cij ） 解个别对换所能解决的数量有限，而通盘考虑，即采用循环换房，形成一个回路，则可使满足需求的住户数达到最大为此引入符号矩阵S （sij ）的概念，S 是邻接矩阵的扩展，其中当第i 类房住户希望换到第j 类房时，sij ij ；否则，sij S ，S S 的元素规定如下：若i ，k 与k ，j 构成一条链，则在链长为的S 中表示为ikj 显然S 对角线上的元素对应于长为 的回路类似规定，可知S ，S 对角线上的元素分别对应长为 ， 的回路由于系统封闭且现有住房已住满，只能在不同回路，即需求循环中寻求换房方案S 中只有一条

10、回路 ，而c ，c ，在这一回路中最多能满足 对住户的换房在C 中删去已实现的需求数得到新的S 及S ，S ，S ，S ，S 只取对角线元素S ，S S S ，S S S S 中有两条回路 ， 中每类房型中分别有 户可换房， 中每类房型中分别有 户可换房S 中只有一条回路 ，该回路中每类房型分别有 户可换房故能满足换房需求的最大住户数为 （ ） 第二节最短路径问题若对图G 的任一边e 赋一实数w （e） ，称为e 的权，则G 连同其边上的权称为加权图或赋权图，记为G （V ，E ，W ） 在实际应用中，边的权可表示道路长度、通过时间、修建费用、允许通过的最大运输量等实际意义设G 为赋权图，H

11、为G 的子图，称W （ H ） e E（ H ）w （e）为H的权许多最优化问题都可归结为在一个赋权图中求某类有最小（大）权的子图其中最短路径问题便是在一个赋权图中求权的总和最小的路径，即求赋权图中路径P ，使minW （ P） e E（ P）w （e） 最短路径问题有广泛的应用价值，例如，各种管道铺设线路的安排、网络输送费用等问题中往往需要求最短路径最短路径算法比其他图论算法研究得更透彻，已有几十种算法最常见的两类最短路径问题是： 求某两已知点间的最短路径，其最好算法是年提出的Dijkstra 算法； 求任意两点间的最短路径，其最好算法是 年提出的Floyd 算法Dijkstra 算法给G

12、（V ，E ，W ）的每个点记一个临时标号T或固定标号P ，T ，P 分别表示从始点v 到该点的最短路径的权的上界和最短路径的权先给v 以P 标号d（v ） ，给其他顶点以T 标号d（v j ） w（v v j ） ，v v j E ， ，v v j 臭E ，j ， ， ，n 一般地，设P v j v j 具有P 标号 ，T v j v j 具有T 标号 V P ，令d（v k ） min v j T d（v j ）为v k的P 标号，则P P v k ，而T唱 v k 中v j 的T 标号修改为d（v j ） min d（v j ） ，d（v k ） w（v k v j ） 当P n 时，求

13、得v 到各顶点的最短路径及其权若v k的P 标号d（v k ） ，则不存在从v 到v k的路径具体实施该算法时，可构造权矩阵D （dij ）n n进行计算，其中dij w（v i v j ） ，v i v j E ， ，v i v j 臭E，i ，j ， ， ，n ，i j ；dii ，i ， ， ，n 例2 某厂按合同要求于下半年每月末依次提供 ， ， ， ， ， 件产品由于原材料、劳动等成本费用的变化，各月单位产品的预计成本依次为 ， ， ， ， ， 又由于库存有限，每月初最多可存放 件产品，且每件每月的存储费为 计划初期已有 件产品，年末合同完成时要求产品库存量为 受生产能力限制，该厂每

14、月只能生产 件产品应如何安排生产计划最有利？解用图唱 表示满足各种限制条件的可能存货状态和状态之间的转换，各边的权是生产和存放费用之和，该多阶段决策问题可归结为求从S 到S 的最短路径，即总费用最小的路径最优安排是各月依次生产 ， ， ， ， ， 件产品，或 ， ， ， ， ， 件产品，总费用为 Dijkstra 算法的计算复杂性是O（n ） ，且对无向赋权图和有向赋权图均适用，但有负权边时，该算法可能失效，需要作适当修改图5唱1在给定的通信网络G （V ，E ，W ）中，已知各弧的可靠性概率值w ij ，往往需要求由网络中指定的信息发出点至接受点的一条总的可靠率最大的路径，称之为最大可靠路，

15、即在G 中寻求路径P ，使maxW （P） 朝e E（ P）w（e） 当G 中某两点不相邻时，可靠率取为 ，令w ij lnw ij ， w ij ，M ， w ij ， ， w ij ，则G （V ，E ，W）中的最短路径即为G 中的最大可靠路实际问题中常有这样的情况，当通过赋权图中某些点时，需要增加附加的费用或时间例如：运输过程中在一些地方装卸时，需要有附加的费用或时间；远洋船停泊在一些港口，通过运河、船闸等都需要附加的费用或时间这类问题称为顶点具有固定费用的最短路径问题，不能用一般最短路径方法求解，需要对原图作适当的修正例3 某城市交通系统中的一段如图唱 所示v 为入口，v为出口，弧上的

16、权表示通过该路段所需时间由于交通设施、路障等，每次转弯需要附加的时间为 求从v 到v 的费时最少的路线第五章图论与网络模型 图5唱2解图唱 中有 条从v 到v 的路径P ：v v v v v v ，时间为 ；P ：v v v v v v ，时间为 ；P ：v v v v v ，时间为 子路径从v 到v 的局部最优解为v v v v v ，不在整体最优解P 中，因此不能直接用Dijkstra 算法求解为此，在v 前增加附加顶点v 及相应弧v v ，在v 后增加附加顶点v 及相应弧v v 给每条弧分配一个虚拟标号L k ，k ， ， ， ，得如图唱 所示的扩充图再生成一个由L ，L ， ，L 作为

17、顶点组成的如图唱所示的转换图，其弧由下列原则确定：若扩充图中L i 有一条直接后继弧L j ，则转换图有弧L i L j ，且w（L i L j ） w（L i ） w P （L i ，L j ） ，其中w（L i ）为扩充图中弧L i的时间，w P （L i ，L j ）是与弧L i ，L j 有关的附加时间由定义，v v ，v v 无时间，v ，v 处也无附加时间应用Dijkstra 算法可求得转换图中从L 到L 的经济路线L L L L L L ，对应于原图中从v 到v 的费时最少的路线v v v v v 图5唱3图5唱4实际规划或工程均包含若干工序，有些工序间是有约束的，即只有某些工序

18、完成后，另外的工序才能开始，而有些工序之间没有直接联系假定这些工序之间的关系和完成每个工序所需时间是已知的，人们希望了解完成整个规划或工程的最少时间以及影响工程进度的关键工序有哪些例4 建造一座楼房底层的工序有 个，各工序所需时间及其相互关系如表唱 所示求最少完工时间和关键工序表5唱1 工序 工序名称测量土地打地基砌墙盖楼板安装电线布设管道粉饰内墙铺地砖时间d 先行工序 ， ， 解法一用顶点v i表示工序i ，用弧v i v j 表示v i完成后v j 才能开始的先后关系，其权表示v i的工时此外，引入虚设工序v 和v ，v 作为v ，v 的先行工序，v 作为v ，v 的后行工序，v v ，v

19、 v 的权均为 ，v v 的权为v 的工时，v v 的权为v 的工时，便得到所谓的工序唱点模型或PT 图，如图唱 所示显然v i的最早开工时间应在以v i为终点的所有工序完成后，如v 最早只能在第 天开始因此v i的最早开工时间即为v 到v i的最长路径之权，工程最早完工时间是从v 到v 的最长路径v v v v v v v 的权图5唱5 该路径也称为关键路径，关键路径上的工序即为关键工序为保证整个工程不延期，任一关键工序均不容许延迟，但非关键工序即使延迟某一段时间也不会影响整个工程的完成非关键工序可延迟的最长时间称为宽裕时间根据关键路径还可求出任一工序的最晚开工时间PT 图中显然无回路，可用

20、最大化方法模拟Dijk唱stra 算法中所用的最小化方法求得最长路径但对任一有向图，此法不一定可行解法二用弧ei表示工序i ，其权表示ei的工时若e i完成后e j 才能开始，则令v k为e i的终点、e j 的始点此外，引入虚设顶点v ，v ，v 作为e ，e 的始点，v 作为e ，e 的终点，便得到所谓的工序唱弧模型或PERT 图，如图唱 所示PERT 图不含回路，工程最早完工时间是从v 到v 的最长路径v e v e v e v e v e v 的权 ，该路径即为关键路径图5唱6PT 图和PERT 图各具特色，且易转换PERT 图的点和边数少些，而PT 图的点数与PERT 图的边数基本相

21、同，故边数较大时PERT 图有优势但PT 图更灵活，能适应一些额外的约束，且计算工序的最早和最晚开工时间更为容易例如，设w i 为工序v i 的工时，v iw i v j 表示v i完成一半后v j 即可开始，v iw i t v j 表示v i完成后经过时间t 后v j 才开始，v t v j 表示时间t 之后v j 才开始，其中v 表示虚设工序求赋权图中任意两点之间的最短路径的问题在生产实际中也有广泛应用例如，航空公司每天要运送很多旅客往来于全国许多城市之间，为了节约，每条航线应使各个旅客的总行程达到最小，这就需要编制一个全国每对城市间的空中最短路径航行里程表求任意两点间最短路径的一个直观

22、方法，就是将图中每个点依次视为始点，用n 次Dijkstra 算法，其计算复杂性是O（n ） ，且使无向图中每条最短路径被计算了两次而Floyd 算法最为有效，且对有负权边但不含负权回路的情况也适用，其计算复杂性是O（n ） Floyd 算法取D（ ） （d（ ）ij ） D （dij ） ，构造D（k） （d（k）ij ） ，其中d（k）ij min d（k ）ij ，d（k ）ik d（k ）kj ，k ， ， ，n d（n）ij 即为从v i到v j 的最短路径的权若计算中出现D（k） D（k ） （k ， ， ，n） ，则停止计算，d（k ）ij 即为从v i到v j 的最短路径的权第

23、三节树连通且无回路的图称为树，记为T 树是最简单且最重要的一类图，具有极大的理论和应用价值 年Kirchhoff 为了解一类描述一个电路的每条支路中和环绕每条回路的电流的线性方程组而发展了树的理论 年Cayley 在计算Cn H n 的同分异构物的数目时也用到了树的理论树的等价定义有： T 连通，且E V ； T 无回路，且E V ； T 的任意两点间仅有一条通路； T 连通，但删去任一边后不再连通； T 无回路，但添加任一新边后仅有一条回路若G 的生成子图为树，则称它为G 的生成树或支撑树显然当且仅当G 连通时，G 有生成树，但一般不唯一可用破圈法和避圈法求连通图的生成树破圈法是通过在一个连

24、通图中，在保持连通性的前提下，破掉所有回路来产生生成树；避圈法是通过在一个连通图中依次选取n 条不构成回路的边来产生生成树设给定n 个城市v ，v ， ，v n ，v i与v j 间直接修建一条铁路的费用为w ij ，试设计一个总费用最低的铁路网把这些城市连接起来这就是所谓的连接问题，它可以归结为在赋权图G （V ，E ，W ）中寻求生成树T ，使minW （T） e Tw （e） ，即找出权最小的连通子图 最小生成树最小生成树问题是图论中许多优化问题的基础求最小生成树常用的有Kruskal 算法（ 年） 、Prim 算法（ 年）和破圈法（ 年） Kruskal 算法将G 的边按权的递增顺序排

25、列后依次检验每条边，若该边与已接纳的边不产生回路，则接纳该边为解的一部分，几条边的权相同时，可先检验其中任一边，直至n 条边被选定，即得最小生成树Prim 算法先从V 中任选一点构成V ，然后在V唱V中选一条到V中某点（比如v ）权最小的边uv 进入解，并令V V u ，直至V V ，即得最小生成树破圈法去掉G 的每个回路中权最大的边，即得最小生成树虽然以上三种算法的计算复杂性均为O（n ） ，但Kruskal 算法和破圈法对边数少的稀疏图更为合适，而Prim 算法只与G 的顶点有关，与G 的稠密度无关，对边数多的稠密图更为适用，且回避了检验回路的要求，也回避了边按其权排序，因此它一般比其他两

26、种算法更有效将G 的边按权的递减次序排列，采用类似Kruskal 算法，也可求得最大生成树例5 在实际的生物学研究中，物种的个数至少有 个，其核苷酸序列的长度至少为 这里考虑一个被缩小了的例子，表唱给定一组物种S ，S ，S ，S ，S 及其核苷酸序列试用一棵树将全部物种连接起来，使得附在树的边上的变化总数尽可能小表5唱2 位置物种 S A G U G U U A A S C A A G U U A A S C G U C C G A A S A A U G U U C A S C G U G U U C U 解该问题可归结为最小生成树问题为此先形成各物种之间的差异数目表，如表唱 所示，应用求

27、最小生成树的算法可求得连接各物种差异总数最小的树，如图唱 所示若图唱 中的权代表一个共同单位，则该树对表唱 的数据而言是最优的但每个权由不同位置的变化所组成，故该树是次优的为了说明这一点，考虑把各个变化情况均显示出来的树，如图唱 所示，约定用i 表示在位置i 处从核苷酸 到核苷酸 的变化若两条相邻的边有一个共同变化，则这种变化的两次出现可通过在树中增加一个顶点而结合起来，以减少一个变化例如，S S 与S S 均有变化CA ，增加顶点S CGUGUUA A ；S S 与S S 均有变化 A G ，增加顶点S A GUGUUCA 从而求得如图唱 所示的变化量减少了 的新树，称为最小种系演化树，S

28、，S 称为Steiner 点表5唱3 S S S S S S S S 图5唱7图5唱8若一个有向图的基础图是树，则称为有向树采用类似破圈法或避圈法可求得有向连通图的生成树但求有向连通赋权图的最小生成树则较复杂，可见参考文献 图5唱9若有向树中仅存在一个入度为 的顶点，且其余顶点的入度为 ，则称该有向树为外向树或根树，其中入度为 的顶点称为树根，出度为 的顶点称为树叶，出度大于 的顶点称为分枝点在实际应用中，根树以根在上，叶在下的方式画出除树叶外，其余顶点的出度最多为m 的根树称为m 元树特别地，出度均为m 的根树称为完全m 元树其中每片树叶v i均赋以正权w i （i ， ， ，t）的赋权完全

29、二元树具有重要应用价值从树根到树叶v i的路径的边数称为路径的长度，记为li 赋权完全二元树带权的路径总长为ti wi li 反之，给定树叶数目及其权值，可构造许多不同的赋权完全二元树，其中带权的路径总长最小的称为最优二元树寻求最优二元树的Huffman 递归算法如下：设t 片树叶的权排序为w w w t ，先连接以w ，w 为权的两片树叶，得一分枝点及其所带权w w ，再在w w ，w ， ，w t中选两个最小的权，连接它们对应的点（不一定都是树叶） ，又得分枝点及其所带的权如此重复，直至形成t 个分枝点，t 片树叶，即得最优二元树该算法的计算复杂性为O（nlnn） 求最优m 元树有类似Hu

30、ffman 算法例6 一个投币机按照预定的顺序来识别所投入的硬币设种硬币 ， ， ， 投入的概率分别为 ， ， ， ，每次投入后经多次二元判断，即可认出投入的硬币假定每次二元判断的时间相同，如何安排判别顺序，使投币机识别硬币的期望时间最短？解构造有 片树叶的二元树，取硬币的出现概率为树叶的权值，w ，w ，w ，w 分别为 ， ， ， ；设每次二元判别时间为t 则该问题归结为求使期望时间t i w i l i最小的二元树采用Huffman 算法求得如图唱（）所示的最优二元树图5唱10第四节设点问题设点问题或选址问题是指在一定区域内为若干服务设施选定位置，使某一指标达到最优值这是一类在规划建设中

31、应用很广泛的问题此处的服务设施可以是医院、消防站、体育中心、商店、电影院、公用电话等公共服务设施，也可以是仓库、转运站、选矿场等生产服务设施，而区域则可通过图的形式来表示服务设施所服务的范围及其联系在设点问题中尽管对选址目标有不同的优化指标，但要求服务对象与服务设施之间易于沟通、易于达到则是共同的一、t唱中心问题例7 某县拟建一个消防站，为该县辖区内n 个城镇服务，如何设置才能使消防站至最远城镇的路径最短？该问题的模型是：在服务区对应的赋权图G （V ，E ，W ）的边v i v j 上求一点v ，使v 的最大服务距离f （v） max k n d（v ，v k ）最小，即min f （v）

32、max k n d（v ，v k ） ，此v 即为所求消防站的选址称v 为G 的唱中心，其中d（v ，v k ） min w ji d（v i ，v k ） ，（ ）w ij d（v j ，v k ） ，w ij 为v i v j 的权，为v 距v i的比例，d（v i ，v k ）为v i与v k之间最短路径的权易证G 的唱中心必位于G 中最长的那条最短路径的中点因此求G 的唱中心问题转化为求G 的任意两点之间的最短路径问题，其计算复杂性为O（n ） _对于急救中心、消防站等紧急型公共服务设施，主要考虑最远的服务对象到服务点的距离尽可能短，使在服务区内能用最短的时间到达目标服务点，适合以中心

33、为指标考虑服务点的设置一般地，t唱中心问题是指t 个服务设施设置在何处最优的问题唱中心问题的模型为：求G 的边上的两点u ，v ，使顶点对u ，v的最大服务距离max k nmind（u ，v k ） ，d（v ，v k ）达到最小，称u ，v为G 的唱中心，其中d（u ，v k ） ，d（v ，v k ）的含义见唱中心问题由于的任意性，该模型无法有效求解若唱中心问题简化为两个服务设施置于G 的顶点v i ，v j ，使max k nmind（v i ，v k ） ，d（v j ，v k ）达到最小，则可有效求解，其计算复杂性为O（n ） 但若仍用类似方法求一般的t唱中心，则计算复杂性为非多项

34、式，至今仍未找到t唱中心的有效算法二、t唱重心问题例8 一个体育中心计划为n 个居民区服务，各居民区的居民数为w k ，k ， ， ，n ，体育中心如何设置，才能使各居民区居民前来参加活动的平均往返路程最短？解设各居民区前来参加活动的人数与该区总人数的比例均为 设体育中心设在其服务区对应的赋权图G （V ，E ，W ，W ）的边v i v j 上点v 处，其中W w k k ， ， ，n为G 中点的权，表示居民区的人数，W w ij e ij E为G 中边的权，表示居民区之间的距离则居民平均往返路程为nk w k d （ v ，v k ） n k w k ，其中d（v ，v k ）的含义见唱中

35、心问题该问题的模型为min f （v） n k w k d（v ，v k ） ，其最优解v 称为G 的唱重心可证G 的唱重心通常位于G 的某一顶点，故min i n f （v i ） nk w k d（v i ，v k ）的最优解即为所求的G的唱重心因此求G 的唱重心问题归结为求G 的任意两点间的最短路径问题对于学校、运动场、图书馆、c2商店、电影院等非紧急型公共服务设施，主要考虑人口密度，使全体服务对象来往的平均路程最短，适合以重心为指标考虑服务点的设置若有t 个设施需设置于非紧急型公共服务网络G （V ，E ，W ，W ）中，使从最近的设施到每一个用户的权重距离的总值最小，则可以建立模型V

36、m 彻inV f （V） n k w k d（V ，v k ） ，且V t ，其中d（V ，v k ） mv iVn d（v ， v k ） 其最优解V称为G 的t唱重心三、1唱重中心问题在实际问题中，有时需要同时考虑重心和中心例如，要求在满足f （v） f 的条件下，使f （v）达到最小，或用f （v） ，f （v）的组合作为目标，如min f （v） f （v） （ ） f （v） ， 这类重心和中心的混合问题称为唱重中心问题第五节网络最大流问题一、最大流许多系统中包含流量问题，如运输系统中有车辆流，控制系统中有信息流，金融系统中有现金流等我们可用网络N （V ，E ，C）这种重要的有向赋

37、权图来描述各种含流量的系统N 中弧v i v j 对应的权cij 表示单位时间内该弧允许通过流动实体的限量，称为容量N中入度为零的顶点称为发点或源，记为v s ，出度为零的顶点称为收点或汇，记为vt ，非源非汇的顶点称为中间点对于多源多汇网络，可增加一个超源vs 和超汇vt ，增加若干条弧vs v si和v t j v t ，容量均为 ，则得一个单源单汇网络设f ij 为弧v i v j 中通过的流量，记f f ij 若f 满足相容条件： f ij cij ，v i v j E ，以及守恒条件：jf ij kf ki ，v i vs ，vt ；jf sj kf kt v（ f ） ，则称f 为

38、可行流，称v（ f ）为可行流f 的流量显然，任一网络均存在可行流如f ij ，v i v j E ，即为一可行流，称为零流网络最大流的基本模型为maxv（ f ） ，s t jf ij kf ki ，v i v s ，v t ，jf sjv（ f），kf kt v（ f ） ， f ij cij ，v i v j E 由此可见，网络最大流问题是线性规划问题的特殊类型由于任一整数弧容量的网络中必存在整数最大流，许多要求整数解的最优化问题可用最大流问题去求解又由于网络的直观性，很多运筹学问题可以直接用网络的形式来构造模型，更易于分析和求解目前网络理论已相当丰富，它在图论的理论研究和实际应用方面有

39、重要意义设N 是一个单源v s 与单汇v t 的网络，f 为N 的可行流，弧流量等于弧容量的弧称为饱和弧，否则称为非饱和弧；弧流量为零的弧称为零流弧，否则称为非零流弧设 是N 对应的无向图中从v s 到vt 的一条路径，定义 的方向是由v s 指向vt ， 上与 同向的弧称为前向弧，其集合记为 ，与 反向的弧称为后向弧，其集合记作 若 中的弧均为非饱和弧， 中的弧均为非零流弧，则称 为关于f 的增广路设V 为V 的非空真子集，V V V ，且v s V ，v t V ，（V ，V ） v i v j v i V ，v j V 称为N 的一个分离v s 与v t 的割切或割集，C（V ，V ）

40、v iv j （V ，V ）c ij 称为（V ，V ）的容量 年Ford 和Fulkerson 给出了最大流最小割切定理：任一网络中最大流的流量等于最小割切的容量，即maxv（ f ） minC（V ，V ） 由此可得推论：可行流f 为网络N 的最大流当且仅当N 中不存在关于f 的增广路因此寻求最大流的关键是解决如何寻找增广路的问题 年Ford 和Fulkerson 提出了寻求网络最大流的标号法：在标号过程中，顶点或是标上号并已检查过（该点有一个标号，且所有与该点相邻的点均已标号） ，或是标上号但未检查，或是未标上号顶点的标号包含两部分，第一个标号表明其标号从哪一点得到，以便找出增广路，第二

41、个标号是为了确定增广路的调整量从任一可行流f 出发，先给v s标号（ ， ） ，此时v s 已标号但未检查，其余点均未标号一般地，任取一已标号而未检查的点vi ，对所有与v i相邻且未标号的点v j ，若v i v j E ，f ij c ij ，则给v j标号（v i ，（v j ） ，其中（v j ） min（v i ） ，c ij f ij 若v j v i E ，f ji ，则给v j 标号（ v i ，（v j ） ，其中（v j ） min（v i ） ，f ji 于是v i成为已标号且已检查的点，v j 成为已标号而未检查的点如此重复，若v t 不能被标号，则不存在关于f 的增广

42、路，f 即为最大流，算法结束若v t 被标号，则从v t 及其第一个标号开始，反向追踪可得增广路 中的弧增加流量（v t ） ， 中的弧减少流量（v t ） ，N 中其余弧的流量不变，便得一流量增加了（v t ）的新可行流去掉所有标号，对新可行流重复上述过程算法本身也给出了求最小割切的方法在求得最大流时，若把所有被标号顶点集合记为V ，未被标号顶点集合记为V ，则可得最小割切（V ，V ） 要想提高总流量，必须首先增大最小割切中弧的容量例9 某公司签订了三项任务合同，每项任务可按期或延期开工，但必须按期或提前完工任务不必从开工到完工连续地干各任务的数据如表唱 所示现有两组工人，规定一个小组每周

43、只干一项任务，且不能两个小组同时干同一项任务，问：所有任务能否按期或提前完工？表5唱4任务开工日期完工日期工期周A 月 日 月 日 B 月 日 月 日 C 月 日 月 日 图5唱11解用顶点v ，v ，v 表示在 月 日至 月 日之间三周的每一周，v ，v ，v 表示任务A ，B ，C 再引入顶点v s ，v t ，建立如图唱 所示的该问题的网络模型，从v s 开始的各弧的容量均为 ，表明每周均可得到两个组 周的工作量在v t 结束的各弧的容量为完成该项任务所需的工作量（以组 周计） 其余弧的容量均为 ，表明可在该周把哪项任务分配给某个小组从零流出发，利用标号法，迭代过程如图唱 所示，弧上的数

44、 数学建模（本科册）表示流量，未标数的弧为零流弧求得最大流量为 ，因此所有任务均能按期完成图5唱12例10 害虫防治机构已找到今年蝗虫迁移的路线如图唱（）所示v s 与v t 分别表示迁移过程的起点与终点，弧容量是基于大量历史数据所预计的飞经该路段的蝗虫的最大数目假设任一路段上的撒药费正比于飞经该路段的蝗虫数，如何杀虫才能使费用最少？图5唱13解该问题可归结为求图唱 （）的最小割集利用标号法可求得如图唱（）所示的一个最大流，此时能被标号的点集为V v s ，v ，v ，不能被标号的点集为V v ，v ，v t ，（V ，V ） v v ，v v 为最小割集，向迁移路段v v ，v v 撒下足够

45、的药粉，第五章图论与网络模型 花费最少Ford唱Fulkerson 标号法中对顶点的标号顺序是任意的，即当图5唱14增广路存在时，其选择方式任意，这可能会产生严重的缺陷考虑如图唱 所示的整数容量的网络（容量为有理数时转化为整数处理） ，用标号法迭代整数有限次，可得整数最大流量但由于标号过程不同，迭代次数也可能有很大差异假定从零流开始，对图唱 交替将v s v v v t 与vs v v vt 用作增广路，则每次增流为 ，需迭代 M 次方得最大流量M ，其中M 为任意正整数这说明标号法的计算复杂性与问题的规模，即点数和边数无关，而是容量的函数Ford 和Fulkerson 还指出当容量为无理数时

46、，其算法可能失效，并给出一个例子，说明算法经过无限次迭代才收敛于最大流量的 Edmonds 和Karp 于 年证明了：若在容量非负的网络中每次沿弧数最少的增广路增流，则最多沿m（n ） 条增广路增流，即可得最大流并对Ford唱Fulkerson 算法进行改进，提出分层标号法，采用“先标号先检查”的原则对顶点进行分类例如，v s为第 类顶点，检查与v s 相邻的所有顶点（得到标号后） ，称为第类顶点，接着检查与第 类顶点相邻的所有顶点（得到标号后） ，称为第 类顶点，依此类推，直到v t 取得标号，并选使流的增值大的顶点对v t 标号这种搜索图的顶点的技术即是所谓的广度优先搜索法（广探法，简记为

47、BFS） 这一改进可确保选得弧数最少的增广路，使得算法的计算步数与容量无关由于一条增广路能在O（m）步内找到，故Edmonds唱Karp 算法的计算复杂性为O（m n） 年Karzanov 给出了一个O（n ）算法， 年Malhotra 又给出了一个较简单的O（n ）算法二、最小流许多网络中容量带有下界限制，网络中的总流量有一个最低 数学建模（本科册）值如在管道运输网络中考虑了管道的阻力或黏性，流量通过每段管道时要求有一个起始的流量，整个系统要求有一个起始的最小总流量，这就是最小流问题设网络N （V ，E ，L） ，L lij v i v j E为各弧流量的下限，最小流问题的基本模型为minv

48、（ f ） ，s t jf ij kf ki ，v i v s ，v t ，jf s j v（ f ） ，kf kt v（ f ） ，lij f ij ，v i v j E 最小流算法先在满足顶点流量平衡条件下进行增流，使橙v i v j E ，有lij fij ，增流的上限不限再构造新网络N （V ，E ，C） ，其中C cij fij lij v i v j E 在N中以C为容量上限求最大流f f ij ，则f f ij fij fij 即为所求N 中的最小流此外，许多情况需要考虑网络中各顶点之间最大流量问题，即多端最大流问题，如交通运输、电话通信、电能分配等系统均存在网络中各顶点对之间皆

49、可以是源和汇的情况虽然可通过逐一地考虑各顶点对之间的最大流来解决多端最大流问题，但需求解Cn次一般最大流问题，较好的算法只需解n 次最大流问题有许多情况需要考虑网络中带有损失或增益的增益流问题，此时流量通过每条弧会得到一个或正或负的增益系数，流从源进入，到汇其总流量也将有很大变化，解一般最大流算法经修正后可用于求解增益网络的最大流也有许多情况需要考虑顶点具有容量的网络最大流问题设网络N （V ，E ，C）中弧vi v j 的容量为cij ，顶点vi的容量为ci ，把vi 分为两个顶点vi 和vi ，并作弧vi vi ，把所有弧第五章图论与网络模型 vk v i 改为vk vi ，vi v j 改为vi vj ，约定vi vi 的容量为ci ，原有各弧的容量仍为cij ，则顶点也具有容量的最大流问题就转化为一般最大流问题三、最小费用流网络流模型中更为一般性的问题是线性最小费用流问题，它给每条弧增加了单位流量费用，并假定费用的增长与流量成线性关系，网络流问题扩展为在总流量达