第五章图论与网络模型

第五章图论与网络模型图论起源于１７３６年Euler对著名的K迸igsberg七桥问题的讨论．由于社会历史条件的限制，在此后的１００多年里发展缓慢．到１９世纪中叶，由于对电网络、晶体模型和分子结构等的研究，图论又重新引起人们的重视．尤其是２０世纪中叶以来，随着数学对各个领域的广泛渗透和计算机的广泛应用，离散数学问题处于越来越重要的地位，图论作为一门提供离散数学模型和求解方法的应用数学学科，新的成果大量涌现．由于图论具有能解决许多用传统数学方法无法解决的问题的特殊功能，以及形象和直观的特点，人们应用图论来解决交通运输、生产规划、经济管理、运筹学、系统论、控制论、信息论、数值分类、计算机科学、通信网络、开关电路、博奕论、地理学、生物学、心理学等领域中的许多实际问题，图论成为一个引人注目的十分活跃的学科．随着实践的发展，其巨大的潜力将会被人们进一步认识、发掘和利用．本章介绍图论的一些基本概念与理论，典型问题和建立图论与网络模型的思路，以及常用的算法．第一节基本概念现实世界的许多现象可用一类图形来描述，这种图形由一个点集和连接该点集中某些点对的边所构成．例如，用点表示车站，边表示车站间道路的交通示意图；用点表示人，边表示一对朋友的人际关系图．对这种图形，人们主要感兴趣的是有哪些点其两点之间能被一条边连接，而点的相对位置及边的长短曲直则无关紧要．大量的这类事实的数学抽象，导致了图的概念．序偶（V，E）称为图，记作G＝（V，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）；有向图中以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阶无向完全图，记为Kn．每个顶点的出度和入度均为n－１的n阶有向图称为n阶有向完全图，也记为Kn．若G的顶点集V可分成两个不相交的非空子集V１，V２，使G的每条边的端点，一个属于V１，另一个属于V２，则称G为二分图或偶图，记为G＝（V１，V２，E）．若简单二分图G＝（V１，V２，E）中V１的每个顶点与V２的所有顶点相邻，则称G为完全二分图，记为Kn，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′导出的子图，记为G［V′］，·１７０·数学建模（本科册）G［V－V′］记为G－V′；若E′彻E，V′含E′中边的全体端点，则称G′为由E′导出的子图，记为G［E′］；从G中删去E′的所有边得到的生成子图记为G－E′，在G上增加E′的所有边得到的图记为G＋E′．G＝（V，E）中的一个点边交替序列μ＝v０e１v１e２v２⋯ekvk称为G的一条通路（有向通路），简记为μ＝v０v１⋯vk，其中ei的端点为vi－１和vi（ei的始点为vi－１，终点为vi），i＝１，２，⋯，k，k称为μ的长．点均不同的通路（有向通路）称为链或路径（有向链或有向路径）．若v０＝vk，则通路（有向通路）称为回路（有向回路），链（有向链）称为圈（有向圈）．若无向图G的任意两点间都存在通路，则称G为连通图．若V分成非空子集V１，V２，⋯，Vr，当且仅当u，v∈Vi时，u与v之间才有通路，则称子图G［V１］，G［V２］，⋯，G［Vr］为G的连通分支．连通分支的个数记为w（G）．对有向图G的任意两点u与v：若存在从u到v及从v到u的通路，则称G是强连通的；若存在从u到v或从v到u的通路，则称G是单向连通的；若不考虑G的边的方向，即G作为无向图是连通的，则称G是弱连通的．设G为无向图，V＝｛v１，v２，⋯，vn｝，E＝｛e１，e２，⋯，em｝．若mij表示vi与ej关联的次数，则称M＝（mij）n×m为G的关联矩阵，M表示G的点与边的关联关系；若aij表示边vivj的重数，则称A＝（aij）n×n为G的邻接矩阵，A表示G的点与点的相邻关系．若G为无环有向图，令mij＝１，ej＝vivk∈E，－１，ej＝vkvi∈E，０，其他，则称M＝（mij）n×m为G的关联矩阵，若aij表示有向边vivj的重数，则称A＝（aij）n×n为G的邻接矩阵．图的矩阵化意味着更适于把图存储在计算机中和对图作数学运算，使人们可从矩阵代数的观点来研究图的性质，同时它也有很多实际应用．例1某房管所将管理的房屋分成４类，设各类房已住满，每年因各种原因有住户要求换房．换房需求如下面的矩阵C＝（cij）所示，其中cij表示第i类房住户要求换到第j类房的需求量．假设系统封闭，要求设计一个换房方案，最大限度满足住户需求．C＝（cij）＝０２０４００７０５３０００４１０．解个别对换所能解决的数量有限，而通盘考虑，即采用循环换房，形成一个回路，则可使满足需求的住户数达到最大．为此引入符号矩阵S＝（sij）的概念，S是邻接矩阵的扩展，其中当第i类房住户希望换到第j类房时，sij＝ij；否则，sij＝０．S＝０１２０１４００２３０３１３２０００４２４３０，S２＝０１４２１２３＋１４３０２３１２３２０００３１２３２３３１４４３１４３２４２３０．S２的元素规定如下：若i，k与k，j构成一条链，则在链长为２的S２中表示为ikj．显然S２对角线上的元素对应于长为２的回路．类似规定，可知S３，S４对角线上的元素分别对应长为３，４的回路．由于系统封闭且现有住房已住满，只能在不同回路，即需求循环中寻求换房方案．S２中只有一条回路２３２，而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为G的子图，称W（H）＝Σe∈E（H）w（e）为H的权．许多最优化问题都可归结为在一个赋权图中求某类有最小（大）权的子图．其中最短路径问题便是在一个赋权图中求权的总和最小的路径，即求赋权图中路径P，使minW（P）＝Σe∈E（P）w（e）．最短路径问题有广泛的应用价值，例如，各种管道铺设线路的安排、网络输送费用等问题中往往需要求最短路径．最短路径算法比其他图论算法研究得更透彻，已有几十种算法．最常见的两类最短路径问题是：①求某两已知点间的最短路径，其最好算法是１９５９年提出的Dijkstra算法；②求任意两点间的最短路径，其最好算法是１９６２年提出的Floyd算法．Dijkstra算法给G＝（V，E，W）的每个点记一个临时标号T或固定标号P，T，P分别表示从始点v１到该点的最短路径的权的上界和最短路径的权．先给v１以P标号d（v１）＝０，给其他顶点以T标号d（vj）＝w（v１vj），v１vj∈E，＋∞，v１vj臭E，j＝２，３，⋯，n．一般地，设P＝｛vj｜vj具有P标号｝，T＝｛vj｜vj具有T标号｝＝V－P，令d（vk）＝minvj∈T｛d（vj）｝为vk的P标号，则P＝P∪｛vk｝，而T唱｛vk｝中vj的T标号修改为d（vj）＝min｛d（vj），d（vk）＋w（vkvj）｝．当｜P｜＝n－１时，求得v１到各顶点的最短路径及其权．若vk的P标号d（vk）＝＋∞，则不存在从v１到vk的路径．具体实施该算法时，可构造权矩阵D＝（dij）n×n进行计算，其中dij＝w（vivj），vivj∈E，＋∞，vivj臭E，i，j＝１，２，⋯，n，i≠j；dii＝０，i＝１，２，⋯，n．例2某厂按合同要求于下半年每月末依次提供１，１，０，３，３，４件产品．由于原材料、劳动等成本费用的变化，各月单位产品的预计成本依次为１１，１３，１３，１２，１４，１３．又由于库存有限，每月初最多可存放５件产品，且每件每月的存储费为１．计划初期已有３件产品，年末合同完成时要求产品库存量为０．受生产能力限制，该厂每月只能生产２件产品．应如何安排生产计划最有利？解用图５唱１表示满足各种限制条件的可能存货状态和状态之间的转换，各边的权是生产和存放费用之和，该多阶段决策问题可归结为求从S１到S７的最短路径，即总费用最小的路径．最优安排是各月依次生产２，０，１，２，２，２件产品，或１，０，２，２，２，２件产品，总费用为１３３．Dijkstra算法的计算复杂性是O（n２），且对无向赋权图和有向赋权图均适用，但有负权边时，该算法可能失效，需要作适当修改．图5唱1在给定的通信网络G＝（V，E，W）中，已知各弧的可靠性概率值wij，往往需要求由网络中指定的信息发出点至接受点的一条总的可靠率最大的路径，称之为最大可靠路，即在G中寻求路径P，使maxW（P）＝朝e∈E（P）w（e）．当G中某两点不相邻时，可靠率取为０，令w′ij＝－lnwij，０＜wij＜１，M，wij＝０，０，wij＝１，则G′＝（V，E，W′）中的最短路径即为G中的最大可靠路．实际问题中常有这样的情况，当通过赋权图中某些点时，需要增加附加的费用或时间．例如：运输过程中在一些地方装卸时，需要有附加的费用或时间；远洋船停泊在一些港口，通过运河、船闸等都需要附加的费用或时间．这类问题称为顶点具有固定费用的最短路径问题，不能用一般最短路径方法求解，需要对原图作适当的修正．例3某城市交通系统中的一段如图５唱２所示．v１为入口，v８为出口，弧上的权表示通过该路段所需时间．由于交通设施、路障等，每次转弯需要附加的时间为３．求从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８．给每条弧分配一个虚拟标号Lk，k＝０，１，⋯，１０，得如图５唱３所示的扩充图．再生成一个由L０，L１，⋯，L１０作为顶点组成的如图５唱４所示的转换图，其弧由下列原则确定：若扩充图中Li有一条直接后继弧Lj，则转换图有弧LiLj，且w（LiLj）＝w（Li）＋wP（Li，Lj），其中w（