运筹学课件图与网络分析

《运筹学课件图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8图与网络分析背景与发现图的基本概念树最短路问题网络最大流问题最小费用最大流问题中国邮递员问题矿山系统工程电子教案6/23/20211图与网络分析概述图论是运筹学的重要分支。图论在物理学、化学、生命科学、信息科学、计算机技术、电气和工程技术、经济学、心理学、社会学、人类学和语言学的某些领域都有应用。事实上，图论为任何一个包含二元关系的系统提供了一个数学模型。这个理论也与数学本身的许多其他分支密切相关，这些分支包括群论、矩阵论、数值分析、概率论、拓扑学和组合学等。随着科技发展和计算机应用，二十世纪五十年代图论得到进一

2、步的发展。将庞大复杂的系统工程问题用图描述，可以解决很多工程设计和管理决策的最优化问题。6/23/20212图与网络分析8.1背景与发现有一种图不屑特定的美学法则，也不是按比例和图例绘制。这种图是由点和线组成的图解或图构，可以用来描述研究对象之间的本质关系，从而达到由表及里、去伪存真的效果。6/23/20213图与网络分析8.1.1背景在实际生活中，为了反映一些人事关系人们常常用点和线画出各种各样的示意图。管线图在许多管线工程技术问题中，专业人员常用几何线形表示管线，并用节点表示管线的交接，从而形成有关的管线图。例

3、如交通网、通讯网、管道网、输电网和电路等。关系图用由点及点间的联线构成的图去反映日常活动中某些人、事或物等对象之间的某种特定的关系。如人际关系、事物的关联等。6/23/20214图与网络分析例8.1铁路干线图北京郑州西安徐州上海济南6/23/20215图与网络分析对阵图v1v2v3v4v56/23/20216图与网络分析图的同构图是反映对象之间关系的一种工具，在一般情况下，图中点的相对位置如何，联线的长短曲直都是无关紧要的。一个图有许多不同的画法，但它们描述的对象及其关系是相同的。设有两个图，若它们的点及其邻接有一

4、一对应的等价关系，则称这两个图是同构的。v1v2v3v4v5v1v2v3v4v56/23/20217图与网络分析箭线图与竞赛图上述两个例子中涉及到的对象之间的“关系”具有“对称性”或“可逆性”，但有许多关系不具有这种对称性。为了反映这一类不可逆的关系，可以用带箭头的联线表示。v1v2v3v4v5v1v2v3v4v56/23/20218图与网络分析统治图(家谱)与树形图有一种结构特殊的图可以用不带箭头的联线明确表示出对象之间的非对称性关系。这种图象棵树，因此称之为树形图。例如统治图、家谱都属于这种图。愚公子辈孙辈部长

5、总统局长6/23/20219图与网络分析《红楼梦》中贾府人物之间的血统关系树贾演贾源贾代化贾代善贾放贾敷贾珍贾蓉贾赦贾政贾琏贾宝玉贾环贾珠贾兰（宁国府）（荣国府）6/23/202110图与网络分析8.1.2发现6/23/202111图与网络分析6/23/202112图与网络分析哥尼斯堡七桥问题哥尼斯堡（曾一度改名加里宁格勒）是欧洲的一个美丽的旅游城市，普莱格尔(Pregel)河从城中穿过，河中有两个小岛。十八世纪时，河两岸及小岛之间共有七座桥。当时那里的居民热衷这样一个问题：一个旅游者能否从某块陆地出发，经过每座桥

6、一次且仅一次，然后回到原地。后来，大数学家欧拉下了断言：此路不通。换句话说，这个问题没有解。6/23/202113图与网络分析七桥问题的沙盘模型6/23/202114图与网络分析一笔画问题在这个问题中，陆地的大小和方位以及桥梁的长短曲直都是无关紧要的；而重要的是两块陆地之间是否有桥梁连接以及有几座桥梁连接。在研究七桥问题时，欧拉根据上述特点将每块陆地用一个点来代替，将一座桥用连接相应两个点的一条线表示，从而得到了一张图。至此，七桥问题就变成通常所说的一笔画问题。欧拉不仅解决了七桥问题，还给出了一个普遍的评定法则：一

7、个图要一笔画出来又回到原处必须满足两个条件，一是所有点要连成一片、二是每个点都与偶数条线相联。6/23/202115图与网络分析千言万语不及一张图起点先出后进中间点先进后出ABCＤＤCAB6/23/202116图与网络分析欧拉图欧拉1739年成功解决这个一度令人神魂颠倒的难题的绝招就是用了这种点线图，这正是“千言万语不及一张图”。后来，人们把能够一笔画出来的图称为“欧拉图”。“欧拉图”在实际中有不少应用，比如邮递员送信的问题。欧拉在解决“七桥问题”时，建立了图论中最初的几个定理，从而使他成为了图论和拓扑学的创始人。

8、6/23/202117图与网络分析哈密顿圈与哈密顿链6/23/202118图与网络分析周游世界英国学者威廉•哈密顿在1859年发明了一种游戏。这种游戏是将一个规则的十二面体的二十个顶点标以世界名城的名称，要求游戏者找一条沿着棱线通过每个顶点正好一次的闭回路。上述问题的解，称为哈密顿圈。含哈密顿圈的图称为哈密顿图。另外，过图中每个顶点恰好一次的链称为哈密顿链。