[教育学]第8章 图与网络分析.ppt

运筹学第8章 图与网络分析 本章知识内容 图的基本概念和模型 树与最小支撑树（最小树问题） 最短路问题 最大流问题 最小费用最大流问题 图论（Theory of Graphs，或Graph Theory）是 运筹学中应用十分广泛的一个分支，是建立和处理离 散数学模型的一个重要工具，其起源最早可以追溯到 1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡 七桥问题”的论文。但是直到20世纪中叶，由于离散 数学问题具有越来越重要的地位，才使图论蓬勃发展 起来。现在图论已经广泛应用于物理学、化学、控制 论、信息论、管理学、销售学、工程技术、交通运输、 教育学及电子计算机等各个领域。 在实际生活、生产和科学研究中，有很多问题可以 用图论的理论和方法来加以解决。例如，在组织生产 中为完成某项生产任务，各工序之间怎样衔接才能使 生产任务完成的既快又好；一个邮递员送信，要走完 他负责投递的全部街道，完成任务后回到邮局，应该 按照怎样的路线投递所走的总路程最短；再如各种通 信线路的合理架设、输油管道的铺设、铁路或公路交 通网络的合理布局等问题，都可以应用图论的方法， 简便、快捷地加以解决。 网络分析（Network Analysis）是图论 的一个重要内容，网络分析最早应用于各种 电路的分析。20世纪50年代以来，由于网络 理论和网络计划方法等研究成果的推广，也 使网络分析在工程设计和管理中得到广泛的 应用，已成为对各种系统进行分析、研究、 管理的重要工具。 哥尼斯堡七桥问题 1736年瑞士科学家欧拉发表了关于 图论方面的第一篇科学论文，解决了著 名的“哥尼斯堡七桥问题”。哥尼斯堡城 有一条河叫普雷格尔河，河中有两个岛 屿，河的两岸和岛屿之间有七座桥相互 连接，如下图所示。 当地的居民热衷于这样一个问题：一个漫步者如何 能够走过这七座桥，并且每座桥只能走过一次，最终回 到出发地。尽管试验者很多，但是都没有取得成功。 为了寻找答案，1736年欧拉将这个问题抽象成下图 所示的一笔画问题。即能否从某一点开始不重复地一笔 画出这个图形，最终回到原点。欧拉在他的论文中证明 了这是不可能的，因为这个图形中每一个顶点都与奇数 条边相连接，不可能将它一笔画出，这就是古典图论中 的第一个著名问题。 第一节 图的基本概念和模型 在实际的生产和生活中，人们为了反映事物及其之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例：下图是我国北京、上海、武汉等14个城市之间的铁路交通图，这里各城市用点表示，用点与点之间的连线表示两城市之间的铁路线。诸如此类的还有城市中的市政管道图、航空线图等等。 例：现有7只球队，拟进行单循环比赛， 它们之间的比赛情况，也可以用图表示出来。 下图就是用点1，2，3，4，5，6，7分别代 表7只球队，用点与点之间的连线表示之间 的比赛。 例：6支球队之间的胜负关系图 从以上的三个例子可以看出：可以用点及点 与点之间的连线所构成的图，去反映实际生产和 生活中的某些对象之间的特定关系。一般来说， 通常用点表示研究对象，用点与点之间的连线表 示研究对象之间的特定关系。由于在一般情况 下，图中点的相对位置如何，点与点之间连线的 长短曲直，对于反映研究对象之间的关系，显的 并不重要，因此，图论中的图与几何图、工程图 等本质上是不同的。 一、图及其图解 1、图的定义 为了区别起见，把两点之间的不带箭头的连线称为边， 带箭头的连线称为弧。这样图就分为无向图和有向图两类。 1）无向图 一个无向图G定义为一个有序二元组（V，E）， 记为 G =（V，E），其中： （1）V是一个有限非空的集合，其元素称为G的结点或顶 点，简称点，而V称为G的结点集或顶点集，简称点集，一 般表示为： （2）E是由V中元素的无序对 所构成 的一个集合，其元素称为G的边，一般表示 为 ，而将E称为G的边 集，一般表示为： 例如，下图是一个无向图G=（V，E） 其中V={v1,v2,v3,v4} E={[v1,v2],[v2,v1],[v2,v3], [v3,v4],[v1,v4],[v2,v4], [v3,v3]} 2）有向图 一个有向图D定义为一个有序二元组（V，A）， 记为 D =（V，A），其中： （1）V是一个有限非空的集合，其元素称为G的 结点或顶点，简称点，而V称为G的结点集或顶 点集，简称点集，一般表示为： （2）A是由V中元素的有序对 所构成 的一个集合，其元素称为D的弧，一般表示 为: ，而将A称为G的弧集,弧集 一般表示为： 下图是一个有向图D=（V，A