文档介绍：该【数学建模--图与网络模型及方法 】是由【才艺人生】上传分享，文档一共【82】页，该文档可以免费在线阅读，需要了解更多关于【数学建模--图与网络模型及方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数学建模--图与网络模型及方法
-62-
-0-
第五章图与网络模型及方法
§1概论
图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。1847年,克希霍夫为了给出电网络方程而引进了“树”的概念。1857年,凯莱在计数烷的同分异构物时,也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈,近几十年来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。哥尼斯堡七桥问题就是一个典型
-62-
-0-
Research)中的一个经典和重要的分支,所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。
我们首先通过一些例子来了解网络优化问题。
例1最短路问题(SPP-shortestpathproblem)
一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错,因此有多种行车路线,这名司机应选择哪条线路呢?假设货柜车的运行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路。
例2公路连接问题
某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来,使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总成本最小?
-62-
-1-
例3指派问题(assignmentproblem)
一家公司经理准备安排名员工去完成项任务,每人一项。由于各员工的特点不同,不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大?
例4中国邮递员问题(CPP-chinesepostmanproblem)
一名邮递员负责投递某个街区的邮件。如何为他(她)设计一条最短的投递路线(从邮局出发,经过投递区内每条街道至少一次,最后返回邮局)?由于这一问题是我国管梅谷教授1960年首先提出的,所以国际上称之为中国邮递员问题。
例5旅行商问题(TSP-travelingsalesmanproblem)
一名推销员准备前往若干城市推销产品。如何为他(她)设计一条最短的旅行路线(从驻地出发,经过每个城市恰好一次,最后返回驻地)?这一问题的研究历史十分悠久,通常称之为旅行商问题。
例6运输问题(transportationproblem)
-62-
-1-
某种原材料有个产地,现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知,单位产品从任一产地到任一工厂的运费已知,那么如何安排运输方案可以使总运输成本最低?
上述问题有两个共同的特点:一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案,数学上把这种问题称为最优化或优化(optimization)问题;二是它们都易于用图形的形式直观地描述和表达,数学上把这种与图相关的结构称为网络(network)。与图和网络相关的最优化问题就是网络最优化或称网络优化(netwokoptimization)问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流(flow)为研究的对象,因此网络优化又常常被称为网络流(networkflows)或网络流规划等。
下面首先简要介绍图与网络的一些基本概念。
-62-
-2-
§2图与网络的基本概念
一个无向图(undirectedgraph)是由一个非空有限集合和中某些元素的无序对集合构成的二元组,记为。其中称为图的顶点集(vertexset)或节点集(nodeset),中的每一个元素称为该图的一个顶点(vertex)或节点(node);称为图的边集(edgeset),中的每一个元素(即中某两个元素的无序对) 记为或,被称为该图的一条从到的边(edge)。
当边时,称为边的端点,并称与相邻(adjacent);边称为与顶点关联(incident)。如果某两条边至少有一个公共端点,则称这两条边在图中相邻。
边上赋权的无向图称为赋权无向图或无向网络(undirectednetwork)。我们对图和网络不作严格区分,因为任何图总是可以赋权的。
一个图称为有限图,如果它的顶点集和边集都有限。图
-62-
-4-
的顶点数用符号或表示,边数用或表示。
当讨论的图只有一个时,总是用来表示这个图。从而在图论符号中我们常略去字母,例如,分别用和代替和。
端点重合为一点的边称为环(loop)。
一个图称为简单图(simplegraph),如果它既没有环也没有两条边连接同一对顶点。
定义一个有向图(directedgraph或digraph)是由一个非空有限集合和中某些元素的有序对集合构成的二元组,记为。其中称为图的顶点集或节点集,中的每一个元素称为该图的一个顶点或节点;称为图的弧集(arcset),中的每一个元素(即中某两个元素的有序对) 记为或,被称为该图的一条从到的弧(arc)。
当弧时,称为的尾(tail),为的头(head),并称弧为的出弧(outgoingarc),为的入弧(incomingarc)。
-62-
-4-
对应于每个有向图,可以在相同顶点集上作一个图,使得对于的每条弧,有一条有相同端点的边与之相对应。这个图称为的基础图。反之,给定任意图,对于它的每个边,给其端点指定一个顺序,从而确定一条弧,由此得到一个有向图,这样的有向图称为的一个定向图。
以下若未指明“有向图”三字,“图”字皆指无向图。
、二分图
每一对不同的顶点都有一条边相连的简单图称为完全图(completegraph)。个顶点的完全图记为。
若,,(这里表示集合中的元素个数),中无相邻顶点对,中亦然,则称为二分图(bipartitegraph);特别地,若,则,则称为完全二分图,记成。
图叫做图的子图(subgraph),记作,如果,。若是的子图,则称为的母图。
的支撑子图(spanningsubgraph,又成生成子图)是指满足
-62-
-6-
的子图。
设,中与关联的边数(每个环算作两条边)称为的度(degree),记作。若是奇数,称是奇顶点(oddpoint);是偶数,称是偶顶点(evenpoint)。关于顶点的度,我们有如下结果:
(i)
(ii)任意一个图的奇顶点的个数是偶数。
,首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。一般来说,算法的好坏与网络的具体表示方法,以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法:邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中,我们首先假设是一个简单有向图,,并假设中的顶点用自然数表示或编号,中的弧用自然数表示
-62-
-7-