第四章图论模型.doc

第四章 图论模型 现实世界的许多实际问题都可以用图形来解释或说明.例如通讯网络就可以用图的形式直观的表现出来：点可以表示通讯中心，而边表示通讯线路.图论模型是应用十分广泛的数学模型,它已经在物理、化学、控制论、信息论、科学管理和计算机等领域.由于它具有图形直观，方法简单容易掌握的特点，因此在实际、生活和数学建模中，有许多问题可以运用图论的理论和方法解决. §4.1图论起源 图论起源于18世纪欧拉对哥尼斯堡七桥问题的研究.哥尼斯堡是18世纪东普鲁士的一个城市，城中有一条普雷格尔河，河中有两个岛，河上有七座桥，如图1所示. 图1 当时那里的居民热终于思考这样一个问题，一个人能否经过七座桥且每座桥只走过一次，最后回到出发点.能否用数学的方法解决这个问题一贯成为当时居民的一个悬而未决的问题. 1736年欧拉创造性的将陆地用点表示，桥用边表示，从而将这个问题转化为如图2所示的一笔画问题，即能否从某个点开始一笔画出这个图形，最后回到原点而不重复.欧拉证明了这个问题是不可能的. 图2 欧拉解决七桥问题时，其方法超出了常用的数学方法，充分发挥自己的想象力，用了全新的思想方法，从而使得问题得到完美解决.由于这一项开创性的工作，产生了“图论”这门崭新学科，欧拉被认为是图论的创始人. §4.2基本概念 定义1 图由两个点集合以及边集合组成，记为，其中： (1)是顶点构成的集合； (2)是连接某些顶点对构成的边组成的集合. 例1 ，，画出图. 图3 注：图分为无向图和有向图. 定义2 若图的边均没有方向，这样的图成为无向图.例如图2，图3为无向图.无向图的边称为无向边，无向边是由两个顶点构成的无序对，无序对通常用圆括号表示. 例2 表示一条无向边，与是同一条边. 定义3 若图的边均有方向，这样的图称为有向图.有向图的边称为有向边，有向边是由两个顶点构成的有序对，有序对通常用尖括号表示.有向边又称为弧. 例3 表示一条有向边，与是两条不同的有向边. 定义4 一条边的端点称为与这条边关联，反之，一条边称为与它的端点关联.与同一条边关联的两个端点是邻接的.如果两边有一个公共端点，则这两条边是邻接的。两个端点重合为一点的边称为圈，不与任何边关联的点成为孤立点. 例4 如图4所示，理解定义4 图4 注：若图中和为有限集，称图G为有限图,没有任何边的图为空图，只有一个点的图称为平凡图。一个图既无圈又没有两边连接同一对点的图称为简单图。 例5 结合图5理解上述概念。 图5 定义5 无向图中前后相继连接的一串边的集合称为路；在有向图中顺向首尾连接的一串有向边的集合称为有向路。通常用顺次的结点表示路。 例6如图6所示: 图6 或构成一条从到的路,但是不构成一条路。 例7 如图7所示： 图7 或为从到的一条路，但是或不构成一条路。 定义6设图是一个简单图，若对图的每条边(弧)都赋一个实数,并称之为该边(弧)的权,这样的赋权图称为网络,记为，其中为的所有边(弧)的权构成的集合。 3 网络的最短路问题 问题描述：对于一个给定的网络,其中每边的权表示该边的长度，那么一个很自然的问题是如何需求网络中某个点到另一个点之间的最短路。在引入最短路算法(Dijkstra算法)前引入以下记号：表示起点到到结点的最短路长度, 表示边的边长(若边不存在则)。 3.1Dijkstra算法 Step1:令,,,。 Step2:在中寻找一点，使得，并令，。 若则算法终止，否则转Step3。 Step3:对中每个点，置，转 step2。 注：该最短路算法执行完毕，起点到任何一点的最短路长度全部求出来。 例8 如图8，求出从到的最短路。 图8 解： 第一次迭代： 第二次迭代： 第三次迭代： 第四次迭代： 第五次迭代： 第六次迭代： 第七次迭代： 第八次迭代： 第九次迭代： 迭代完毕，最短路的长度为9，最短路的路径为或。 3.2最短路问题的应用 1设备更新问题 某工厂使用一台设备，每年年初工厂要作出决定：是继续使用旧设备还是更换新设备？如果继续使用就设备就需要支付维修费；如果使用新设备就需要支付设备费。试确定一个5年计划，使得总支出费用达到最小。设备在各年的够买费以及机器在不同役龄的维修费如表1所示。 项目 第1年 第2年 第3年 第4年 第5年 购买费 11 12 13 14 14 机器役龄 0-1 1-2 2-3 3-4 4-5 维修费 5 6 8 11 18