《图论模型.ppt

图论模型 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。 图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。 哥尼斯堡七桥问题就是一个典型的例子。 在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来. 问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。 当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。 欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。 问题成为从任一点出发一笔画出七条线再回到起点。 欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联. 将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。。 图与网络是运筹学中的一个经典和重要的分支，所研究的问题涉及: 经济管理 工业工程 交通运输 计算机科学与信息技术 通讯与网络技术等诸多领域 下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 最短路问题 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？ 指派问题 一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？ 中国邮递员问题 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？ 由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。 旅行商问题 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。 运输问题 某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？ 例1 证明任何6个人中，其中总存在3个人，他们或者相互认识或者相互不认识. 例2 9名数学家在一次国际数学会议上相遇，已知他们任意3个人中至少有两个可以用一种语言对话，且每个数学家至多会说3种语言，证明至少存在在3名数学家可以用同一种语言对话. 例3 有4对夫妇参加一次舞会，会间某些人两两做舞伴跳舞（夫妇之间没跳过舞）.会后，其中一位赵先生统计其余每位与会者跳舞的次数，发现他们跳舞的次数各不相同，问：（1）赵夫人跳了几次舞？（2）赵先生跳了几次舞？（3）谁与谁是夫妻？ 课后练： IMO评议会有34个国家参加，每个国家有领队和副领队两个人参加，会前某些与会者之间握手相互问候（领队与他的副手不握手）.会后，主办国领队统计其余每位与会者握手的次数，发现他们握手的次数各不相同，问：主办国副领队与多少个人握过手.(IMO26) 一、图的概念 每对顶点之间的最短路 计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。 具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为大。 第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。 二、建模案例：最优截断切割问题 邻接矩阵 注：假设图为简单图 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 返回 Evaluation only. Created with Aspose.Slides for