图论与网络分析

第1页，共29页，2023年，2月20日，星期四第七章图论与网络分析运用图论中的分析技术可以解决现实世界的许多问题，如交通网、管道网、通信网的优化以及工程进度安排等问题。除此之外，还有很多问题，从表面上看似乎与网络毫无关系，但实质上也可以用网络模型来描写，例如设备更新的优化问题，就可以表述为网络分析中的最短路问题。通过学习本章，应当了解图与网络的基本概念；掌握最短路问题、最大流问题和最小费用最大流问题的图论解法，并会对管理中的实际问题进行分析判别其是哪一类图论问题；学会运用WinQSB来求解经济管理中的图与网络问题。2第2页，共29页，2023年，2月20日，星期四第一节图的基本概念及图的模型一、图的基本概念及图的模型概述瑞士数学家欧拉(E.Euler)在1736年发表了一篇题为“依据几何位置的解题方法”的论文，有效地解决了哥尼斯堡七桥难题，这是有记载的第一篇图论论文，欧拉被公认为图论的创始人。18世纪的哥尼斯堡城中流过一条河(普列格河)。河上有七座桥连接着河的两岸和河中的两个小岛，如图7-1(a)所示。欧拉将此问题归结为图7-1(b)，这是一个用图的模型来描述和解决实际问题的第一个著名例子。3第3页，共29页，2023年，2月20日，星期四一、图的基本概念及图的模型概述1857年英国数学家哈密顿(Hamilton)发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座城市，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。它与七桥问题不同，前者要在图中找一条经过每边一次且仅一次的路，通称欧拉回路，而后者是要在图中找一条经过每个点一次且仅一次的路，通称为哈密尔顿回路。哈密尔顿根据这个问题的特点，给出了一种解法，如图7-2粗箭线所示。4第4页，共29页，2023年，2月20日，星期四二、图模型举例例7-1化工品的贮存问题。现要求贮藏8种化工品A，B，C，D，P，R，S，T。出于安全的原因，下面各组产品不能放在一起：A-R，A-C，A-T，R-P，P-S，S-T，T-B，B-D，D-C，R-S，R-B，P-D，S-C，S-D。问题：贮藏这8种化工品至少需要多少间贮藏室？解（参见教材P164）例7-2农夫、狼、羊、草过河问题。有位农夫，携带一匹狼、一只羊和一挑草要过一条小河，河中只有一条小船，一次摆渡农夫只能携带一样东西。当农夫不在场时，狼要吃羊，羊要吃草。试问：农夫怎样才能将这三样东西摆渡到对岸？至少要摆渡几次？解（参见教材P165）5第5页，共29页，2023年，2月20日，星期四第二节图论中的基本概念6第6页，共29页，2023年，2月20日，星期四第二节图论中的基本概念在图7-6中“相互认识”用两条反向的弧来表示。7第7页，共29页，2023年，2月20日，星期四第三节最短路问题8第8页，共29页，2023年，2月20日，星期四一、求解最短路问题的狄克斯托算法9第9页，共29页，2023年，2月20日，星期四一、求解最短路问题的狄克斯托算法10第10页，共29页，2023年，2月20日，星期四二、最短路问题的应用解（参见教材P171）11第11页，共29页，2023年，2月20日，星期四二、最短路问题的应用解（参见教材P173）12第12页，共29页，2023年，2月20日，星期四第四节最小生成树问题树是图论中结构最简单但又十分重要的图，在自然科学和社会科学的许多领域都有广泛的应用。例如，在架设电话线、铺设自来水管道或暖气管道的工程设计中会遇到如下的优化问题：如何使通话点或者取水取暖点相互连通，但总的线路长度最短。这类问题在网络分析中称为最小生成树问题。13第13页，共29页，2023年，2月20日，星期四一、求解最小生成树问题的破圈算法和避圈算法(一)树的概念和性质(二)生成树和最小生成树14第14页，共29页，2023年，2月20日，星期四一、求解最小生成树问题的破圈算法和避圈算法(三)求解最小生成树的破圈算法和避圈算法1．破圈法具体步骤如下。(1) 在给定的赋权的连通图上任找一个圈。(2) 在所找的圈中去掉一条权数最大的边(如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条)。(3) 如果所余下的图已不含圈，则计算结束，所余下的图即为最小生成树。否则返回步骤(1)。15第15页，共29页，2023年，2月20日，星期四一、求解最小生成树问题的破圈算法和避圈算法2．避圈法初始选一条最小权的边，以后每一步中总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈(每一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条)。具体步骤如下。(1) 在给定的赋权的连通图上选取一条最小权的边。(2) 从未被选取的边中选取一条权最小的边，并使之与已选取的边不构成圈。如果有两条或两条以上的边都是权最小的边，则从中任选一条。(3) 重复步骤(2)。如果这样的边不存在，则计算结束。16第16页，共29页，2023年，2月20日，星期四二、最小生成树问题的应用解（参见教材P179）17第17页，共29页，2023年，2月20日，星期四第五节最大流问题最大流问题是一类应用极为广泛的问题。例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，等等。对于这些包含了流量问题的系统，往往要求求出其系统的最大流量。例如，某公路系统容许通过的最多车辆数、某供水系统的最大水流量等，以便我们加深对某个系统的认识并加以改造。所谓最大流问题就是：给了一个带收发点的网络，其每条弧的赋权称为容量，在不超过每条弧容量的前提下，求出从发点到收点的最大流量。18第18页，共29页，2023年，2月20日，星期四一、最大流的数学模型解（参见教材P181）19第19页，共29页，2023年，2月20日，星期四二、最大流问题的网络图论解法(一)对网络上弧的容量的表示作改进(二)求最大流的基本算法20第20页，共29页，2023年，2月20日，星期四第六节最小费用最大流问题在前面讨论的最大流问题中没有涉及费用问题。但在实际生活中，各种物质的流都是与费用有关的。如一辆载货汽车经过不同的路线，可能要交不同的过路费、过桥费等，这样对于司机来说就有一个到达某一目的地走哪条路线最省钱的问题。最小费用最大流就是这样的问题。所谓最小费用最大流问题就是：给了一个带收发点的网络，对于每条弧，除了给出了容量外，还给出了这条弧的单位流量的费用，要求一个最大流F，并使得总运送费用最小。21第21页，共29页，2023年，2月20日，星期四一、最小费用最大流的数学模型解（参见教材P186）22第22页，共29页，2023年，2月20日，星期四二、最小费用最大流的网络图论解法(一)对网络上弧的容量和单位流量费用的表示作改进(二)求最小费用最大流的基本算法23第23页，共29页，2023年，2月20日，星期四第七节中国邮递员问题一、哥尼斯堡七桥问题与欧拉图定理1无向连通图G是欧拉图，当且仅当G中无奇点。(证明从略)定理2连通有向图D是欧拉图，当且仅当它每个顶点的出次等于入次。与七桥问题类似的还有一笔画的问题。给出一个图形，要求判定是否可以一笔画出。一种是经过每边一次且仅一次到另一点停止，另一种是经过每边一次且仅一次回到原出发点。这两种情况可分别用欧拉道路和欧拉回路的判定条件加以解决。24第24页，共29页，2023年，2月20日，星期四二、中国邮递员问题中国邮递员问题是欧拉回路问题的扩展，它是由中国数学家管梅谷先生在1962年提出的，因此国际上通称为中国邮递员问题。一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问：应如何安排送信的路线使所走的总路程最短？用图论的语言来描述：给定一个连通图G，每边有非负权，要求一条回路过每边至少一次，且满足总权最小。25第25页，共29页，2023年，2月20日，星期四三、求解中国邮递员问题的奇偶点图作业法及其改进(一)求解中国邮递员问题的奇偶点图作业法(1) 如何构造第一个可行方案。(2) 寻找改进的可行方案。(二)奇偶点图作业法的改进方法26第26页，共29页，2023