第六章图与网络分析.pptVIP

第六章 图与网络分析 引言 图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。 引言 　　1736年瑞士科学家欧拉(1707-1783)发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图a所示。 引言 　　当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。 　　为了寻找答案，1736年欧拉将这个问题抽象成图b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。 图的基本概念与模型 　　　图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。 图的基本概念与模型 图的基本概念与模型 　定义: 图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1]； e2=[v1,v2]。 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的模型应用 图的基本概念与模型 　解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。 图的基本概念与模型 一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。 图的基本概念与模型 思考题解答： 以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如C—E—A—F—D—B，就是一个符合要求的考试课程表。 树与图的最小树 树与图的最小树 例 某企业的组织机构图也可用树图表示。 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 求树的方法：破圈法和避圈法 树与图的最小树 树与图的最小树 树与图的最小树 赋权图中求最小树的方法：破圈法和避圈法 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 课堂练习： 树与图的最小树 最短路问题 问题描述： 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。 最短路问题 求最短路有两种算法: 最短路问题 狄克斯屈拉(Dijkstra)标号算法的基本思路： 若序列{ vs，v1 ， …，vn-1，vn }是从vs到vn间的最短路，则序列{ vs，v1 ， …，vn-1 } 必为从vs 到vn-1的最短路。 最短路问题 以vi为起点vj为终点的边记为 [i, j]，其距离为dij 显然dii=0 若i与 j不相邻，则dij=∞ 若用Lsi表示从点s到点i的最短距离，若求起点是vs ，终点是vt的图的最短路， dijkstra算法步骤如下：