图论-数学建模

《图论-数学建模》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论山东建筑大学贺长伟1引言图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。

2、问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的

3、结果，不但彻底解决了这个问题，而且开创了图论研究的先河。我们首先通过一些例子来了解网络优化问题。例1最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。例2公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或

4、间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？例3指派问题（assignmentproblem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？例4中国邮递员问题（CPP－chinesepostmanproblem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局

5、出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提的，所以国际上称之为中国邮递员问题。例5运输问题（transportationproblem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问

6、题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（netwokoptimization）问题。2图与网络的基本概念2.1无向图一个无向图(undirectedgraph)是由一个非空有限集合和中某些元素的无序对集合构成的二元组，记为。其中称为图的顶点集（vertexset）或节点集（nodeset），中的每一个元素称为该图的一个顶点（verte

7、x）或节点（node）；称为图的边集（edgeset），中的每一个元素记为或，被称为该图的一条从到的边（edge）一个图称为有限图，如果它的顶点集和边集都有限。图的顶点数用符号或表示，边数用或表示。当讨论的图只有一个时，总是用G来表示这个图。从而在图论符号中我们常略去字母G，例如:分别用代替。端点重合为一点的边称为环(loop)。一个图称为简单图(simplegraph)，如果它既没有环也没有两条边连接同一对顶点。2.2有向图定义一个有向图（directedgraph或digraph）G是由一个

8、非空有限集合V和V中某些元素的有序对集合构成的二元组，记为其中称为图的顶点集或节点集.称为图的弧集（arcset），A中的每一个元素(即中某两个元素的有序对)记为或，当弧时，称为尾（tail），为头（head）.2.3完全图、二分图每一对不同的顶点都有一条边相连的简单图称为完全图(completegraph)。n个顶点的完全图记为。若，，（这里表示集合X中的元素个数），X中无相邻顶点对，Y中亦然，则称G为二分图(bipartitegraph)；特别地，若，则，则称G为完全二分图，记成。2.4子图