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