资源描述：
《运筹学6.图与网络分析-最短路》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章图与网络分析图的基本概念与基本定理树和最小支撑树最短路问题网络最大流本章内容重点引言图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。引言随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如
2、果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。引言1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图1a所示。引言AB图1aCD引言当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1
3、736年欧拉将这个问题抽象成图1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。引言图1bACDB在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例：公路或铁路交通图、管网图、通讯联络图等各节点及联系的边。如果用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合G={V,E}式
4、中：V—点的集合,E—边的集合如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等这样的图称为网络图。1.图的基本概念与模型用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。如图6-1所示：端点，关联边，相邻环，多重边，简单图次，奇点，偶点，孤立点链
5、，圈，路，回路，连通图完全图，偶图子图，部分图例12.树和最小支撑树树图（简称树，记作T（V,E））在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。性质1任何树中必存在次为1的点。性质2具有n个顶点的树的边数恰好为（n-1）条。性质3任何具有n个点、（n-1）条边的连通图是树图。2.1树的性质2.2图的最小部分树如果G1是G2的部分图，则称G1是G2的部分树（或支撑树）。树图的各条边称为树枝（假定各边均有权重），一般图G2含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（也
6、称最小支撑树）定理1图中任一个点i，若j是与i相邻点中距离最近的，则边[i,j]一定必含在该图的最小部分树内。推论把图的所有点分成V和两个集合，则两集合之间连线的最短边一定含在最小部分树内。练习:写下图的树图v6v5v2v3v4v1v6v5v2v3v4v1练习用破圈法求出下图的一个树图。V5V4V2V3V1e6e5e4e3e2e1e7e8取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4v5,v3）中去掉边e6。再
7、从圈(v1,v2,v5,v4,v3,v1）中去掉边e7，这样，剩下的图不含圈，于是得到一个支撑树，如下图所示。v2e1e2e5e8v1v3v42.3避圈法和破圈法（1）避圈法从网络图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。在图中寻找最小部分树的步骤：P153（2）破圈法①在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；②去掉该圈中权数最大的边；反复重复①②两步
8、，直到最短树。练习：用破圈法求出下图的最小部分树图av6v5v2v3v4v1627535441v3v2v1v4v6v553142图b最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是：设为连通图，图中各边有权(表示，之间没有边）,为图中任意两点，求一条道路，使它是从到的所有路中总权最小的路。即
