图论的应用计算机技术与科学毕业论文.doc

2010届学生毕业设计(论文)材料（四）学 生 毕 业 设 计（论 文）课题名称图 论 的 应 用姓 名学 号0609302-18院 系数学与计算科学系专 业信息与计算科学指导教师2010年 5 月5日目录 摘要.1 关键词.1 Abstract.1 Key words.1 引言.21.图论的发展 . 32. 图论的基本理论知识 .4 2.1 拓扑序列.4 2.2 欧拉回路.4 2.3 最大流 .53. 运用图论对实际生活中的具体问题进行分析.5 3.1 图论在高校选课中的应用.5 3.2 图论在单词接龙中的应用.63.3 图论在邮政中的应用.74. 总结 .9参考文献.9 致谢.10 图论的应用摘要：图论从诞生至今已有200多年的历史，但很多问题一直没有很好地解决。随着计算机科学的发展，图论又重新成为了人们研究讨论的热点。图形是一种描述和解决问题直观有效的手段，这里给出图论在现实生活中的一些应用。关键字：图论；拓扑有序序列；欧拉；最大流；On Graph Theory and Its Application Liu Xiao-yiAbstract: From the birth of graph theory has been 200 years of history, but has not been a good lot of problems to solve. With the development of computer science, graph theory has again become a hot topic that people study. Graph is a visual description and effective means to solve the problem, here is given graph theory in real life some of the application.Key words：Graph Theory；Ordered sequence of topological ;Euler; Maximum flow;引言虽然最早的图论间题追溯1736年(哥尼斯堡七桥间题)，而且在19世纪关于图论的许多重要结论已得出。但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和传播。图论即形象地用一些点以及点与点之间的连线构成的图或网络来表示具体问题。利用图与网络的特点来解决系统中的问题，比用线性规划等其他模型来求解往往要简单、有效得多。图论就是研究图和网络模型特点、性质和方法的理论。图论在许多领域,诸如物理、化学、运学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理等各方面都有广泛的应用,它已经广泛地应用于实际生活、生产和科学研究中。图论可以解决一些看似很难实际上却很简单的问题。 例如,某公司现在正经历一次罢工,为了使公司在罢工中照常运作,人事部确定了 4项关键工作:销售维修、安全控制和会计,其中销售需要 2人。表 1给出了每个人和他们能胜任的工作,判断是否所有工作都能有人来负责,设每人只能负责一项工作。 表1 每个人与他们胜任的工作A会计 销售B销售 安全控制C销售 安全控制 维修D维修 E安全 维修这看起来是社会学领域的问题 我们可以尝试多种方法 而其中的一种方法就是将其化为图，建立一个图的模型。最基本的问题是如何描述它，什么是结点？什么是边？在本问题中 没有太多的选择，只有人和工作。我们可试着用集合中的结点来代表X人，用集合中的结点来代表工作。用边来代表图Y中结点之间的关系，在这里结点之间的关系是“人能否胜任工作”因此 若某人能胜任工点作，那么就在两个结点之间加上一条边。由于销售需要2人，所以用2个结S1和S2表示。如此得到二分图（I）给出了最大匹配，很容易看出每一项工作都有人来负责。 集集 再例如一个部门中有25人，由于纠纷而使得关系十分紧张，是否可便每个人与5个人相处融洽?则可以建立一个图的模型，最基本的问题是如何描述它什么是结点，什么是边?在本问题中，没有太多的选择，只有人和纠纷。我们可试着用结点来代表人。用边来代表图中结点之间的关系，这是很常见的。在这里结点之间的关系是“关系是否融洽”，因此，若两个结点(人)关系融洽，那么就在它们之间加上一条边。现在假设每个人与其他5个人关系融洽。在图1上显示出我们所描述的图的一部分，小张与小王、小李、小赵、小黄和小吴关系融洽，再没有其他人。25个人均是这种情况。 小张小王小李小赵小黄小吴图1 这是否可能?在图论中，一个重要的推论:在任意图中，具有奇数度的结点个数必为偶数。现在出现了矛盾:有25(奇数)个具有5(奇数)度的结点。因此，该间题是不可能实现的。1、图论的发展：图论产生和发展历经了二百多年的历史，大体上可以划分为三个阶段。第一阶段是从 1736 年到十九世纪中叶。这时的图论处于萌芽阶段, 多数问题是围绕着游戏产生的， 最具有代表性的工作是著名的瑞士数学家L. Euler 于 1736 年的 Konigsberg七桥问题。他的那篇论文被公认为图论历史上第一篇论文。第二阶段从十九世纪中叶到1936 年。这个时期中图论问题大量出现, 如四色问(1852 年)和Hamilton 问题(1856 年)。同时出现了以图为工具去解决其它领域中一些问题的成果。最有代表性的工作是Kirchhoff(1847年)和Cayley(1857 年)分别用树的概念去研究电网络方程组问题和有机化学的分子结构问题。“图(Graph)”这个词第一次出现是在1878 年的英国自然杂志中。进入本世纪三十年代, 出现了一大批精彩的新理论和结果,如Menger定理(1927 年) ，Kuratow ski 定理(1930 年)和Ram sey 定理(1930 年)等等。这些理论和结果为图论作为一个数分支奠定了基础。1936 年，匈牙利数学家D. Konig 写出了第一篇图论论文到1936 年第一本图论专著有限图与无限图的理论。至此, 图论作为数学的一个分支已基本形成。从1736 年的第一篇图论论文到 1936 第一本图论专著, 整整经历了二百年。图论 1736 1936 对这段历史作了详尽的回顾与研究。1936 年以后是第三阶段。由于生产管理、军事、交通运输、计算机和通讯网络等方面的需要提出一系列问题， 特别是许多离散性问题的出现大大促进了论的发展。进入七十年代以后， 特别是大型电子计算机的出现， 使大规模问题的求解成为可能，图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面的应用研究都得到了很大的发展。图论越来越受到全世界数学界和其它科学界的广泛重视。各种国际学术交流活动十分活跃。大型国际会议频频召开， 国际图论杂志也于1977 年创刊。目前， 发表图论论文的专业杂志有十几份之多，其论文数目每年呈指数型上升。图论以及应用的专著已多得无法统计。就其图论本身来讲， 现已发展成代数图论、拓扑图论、随机图论、计数图论、算法图论、无限图论等多个分支多个学术派别的现代数学学科。由于图论的重要性，越来越多的高等院校已把它列为数学、计算机科学、电子学和科学管理等专业本科生的必修课和选修课。以考察高校本科生的数学基础和综合应用能力为主的美国大学生数学建模竞赛，从 1985 年开赛以来共二十二个竞赛题中，有14 的问题须借助于图论这个数学工具才能解决。目前，我国高等院校理工科非数学专业所学的数学课程,如高等数学、线性代数所授内容基本上都是二十世纪以前的数学内容，对现代数学和现代数学方法基本上没有涉及。在这个迈向新世纪的年代，我们面临加快现代化建设, 深化教学改革的任务。教学领域迫切需要加强课程建设，引进当代科技发展的新成果，更新和优化教学内容，培养跨世纪的人才。图论及其应用课程的开设正是为着这个目的， 它对拓宽学生的知识面，优化学生的知识和能力结构很有必要。 2、图论基本理论知识：图论（graph theory）是数学的一个分支，它以图（graph）为研究对象，研究顶点（vertex）和边（edge，又称line）组成的图形的数学理论和方法。图论作为一个数学分支，有一套完整的体系和广泛的内容，这里只介绍本文所涉及的图论的一些基本理论，其目的在于为后面的研究做铺垫，可以以图论的基本知识作为工具来指导解决实际问题。2.1 拓扑序列 设是简单有向图,其是顶点的有穷非空集合,是有向边的集合.若,则表示从顶点到顶点的一条有向边,且称是有向边的初始点,是有向边的终结点,是的先驱,是的后继.顶点的度是和相关的边的数目;以顶点为初始点的有向边的数目称为的出度;以顶点为终结点的有向边的数目称为的入度。定义1：设是有限有向简单图,若存在顶点集上的一种标顺序,得到一个顶点序列,使得对于任意的,顶点一定不是顶点的先驱,则称该顶点序列为拓扑有序序列.定理1：有限有向图存在拓扑有序序列的必要条件是中至少存在一个顶点,其入度为0. 定理2：有限有向图存在拓扑有序序列当且仅当中无回路.推论：是有向树或森林当且仅当有向图存在拓扑有序序列.2.2 欧拉回路 定义2：通过图的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图,称为欧拉图。定理3：无向连通图是欧拉图不含奇数度的结点(即的所有结点的度均为偶数)。定理4：一个连通(弱连通: 如果不考虑有向图中边的方向所得到的无向图是连通图，则有向图称为弱连通图。)有向图具有欧拉回路的充要条件是的每一个结点的入度和出度相等。具有欧拉路的充要条件是除起点和终点外,每个结点的入度等于出度。对于起点，其出度比入度多1,对于终点，其出度比入度少1。2.3 最大流 图论中的图是由点及点之间的连线构成的，反观世界中某些对象之间的某个特定的关系。用点表示所研究的对象，用点与点之间的连线这两个对象之间有特定的关系。在实际问题时不仅要表示两个对象之间有无关系，还要这两个对象之间的数量，如距离、时间、费用称之为权，则图连同边上的权称为赋权图。如果对图的任何两个顶点和，中存在一条的路，则称为连通图。如果没有规定方向，连通图中只各点，且总长最短的问题即为最小数问题。如规定了方向时则称为最短路问题，对于连接两个城市的所有公路连接形成的整个网络来说，两个城市之间的最大通行能力即为最大流问题。所谓最大流问题就是在容量网络中,寻找流量最大的可行流.定义3 设为有向图,在中指定一点称为发点(记为 ),和另一点称为收点(记为 ),其余点叫做中间点. 对每一条边,对应一个非负实数 ,称为它的容量.这样的称为容量网络,简称网络,记作.定义4 网络中任一条边有流量 ,称集合 为网络上的一个流.满足下述条件的流 称为可行流： (限制条件)对每一边 ,有 ; (平衡条件)对于中间点有 , 即中间点的输入量 = 输出量. 如果 是可行流,则对收、发点、有 ,即从点发出的物质总量 点输入的量. 称为网络流 f 的总流量. 上述概念可以这样来理解,如是一个运输网络,则发点表示发送站,收点表示接收站,中间点表示中间转运站,可行流 表示某条运输线上通过的运输量,容量表示某条运输线能承担的最大运输量, 表示运输总量.可行流总是存在的.比如所有边的流量 就是一个可行流(称为零流).3、运用图论对实际生活中的具体问题进行的分析：3.1 图论在高校选课中的应用背景：随着高校教学体制改革,越来越多的高校实行了学分制.在学分制度下,学生只要选修一定量的课程,修完规定的学分,即可毕业.其中有一部分课程是必修课,是培养专业素质的根基.在必修课程中,有些是基础课,它们独立于其他课程,必须先修;而另一些是后续课程,必须在学完作为它的基础的先修课程以后,才能开始.这些先决条件决定了课程之间的领先关系.因此,每个专业的学生在选修必修课程时,必需考虑到课程之间的领先关系.研究选课问题具有重要的现实意义。模型建立：课程之间领先关系的抽象我们利用图论中有向无回路图的有关知识,把课程之间领先关系转化为有向无回路图中的有向边.其构造有向无回路图的方法是:图中的顶点表示课程,有向边表示课程之间的领先关系;若课程x是课程y的先决条件,则图中出现从顶点x到顶点y的有向边.选课问题的抽象借助有向无回路图,我们可把选课问题抽象为在有向无回路图中寻找拓扑有序序列.实行学分制的各个院系,在按排教学计划时,必须考虑到课程之间的领先关系,首先把该专业必修课程之间的依靠关系抽象为有向无回路图,然后从有向无回路图中找到多个拓扑有序序列。通过把课程之间领先关系转化为有向无回路图,进而把选课问题转化为在有向无回路图中寻找拓扑有序序列问题,从而成功地解决了高校学生的选课问题。例如，某校计算机专业的必修课程之间的领先关系如表2。 表2：某校计算机专业必修课程课程编号 课程名 先决条件 程序设计基础 无 离散数学 数据结构 ， 汇编语言 语言的设计和分析 ， 计算机原理 编译原理 ， 操作系统 ， 高等数学 无 线性代数 普通物理 数值分析 ， 首先，可以根据领先关系构造出有向无回路图，如图2。图2 然后，根据有向无回路图寻找拓扑有序序列。在图2中，按照找拓扑有序序列的方法，可以找到拓扑有序序列：。当然，有向无回路图中的拓扑有序序列不只一个，对于图2，还可以找到拓扑有序序列：。所以，该专业的学生可以根据这些拓扑有序序列中一个来选课。 3.2 图论在单词接龙中的应用背景：有这样一个古老的数学问题。假设有许多张卡片,每张卡片上都写着一个英文单词,现在要把这些卡片按照一定的顺序连成串。这个顺序要求每张卡片(第一张卡片可以除外)上的单词的首字母恰好是前一张卡片上的单词的尾字母,并且要求每张卡片只能用一次,简单地说就是“单词接龙”。有一些单词组通过适当的组合是可以完成接龙的,例如,“teach”，“teeth”，“yet”，“happy”。但是某些单词组却不具备这样的性质,比如“ok”，“old”，“deep”，“king”。问题的关键是能否找出一种科学的方法快速、准确地判断一组单词是否可以按照上述规则完成接龙呢?可以运用图论中的欧拉定理建立了数学模型,来求解该问题。对任意一组单词,可以判断出它们能否完成接龙。模型建立：假设不区分字母的大小写，可以把所有的英文字母看成是26个节点，把每一个单词看作是一条有向边，即弧。这样,弧头就是单词的首字母，弧尾就是单词的尾字母，且弧头、弧尾必然都在AZ这26个点当中。一组单词就可以构成一个节点数有限的有向图，模型建立起来了，而判断单词能否完成接龙的问题也就转化成了一个图论问题，即判断一个有向图中是否存在欧拉回路或者欧拉路。而且由于图的点数最多为26个，若经过合理地设计，算法的复杂度可降到常数级。可以对定理做一个简单地应用。“teeth”、“teach”、“happy”、“yet”这4个单词可以完成接龙，即teethhappyyetteach，它们构成的有向图如图3所示。“old”、“ok”、“king”、“deep”这4个单词无法完成接龙，它们构成的有向图如图4所示。这是观察的结果，可以再从图论的角度证明之。若能一笔把这些单词连起来，则所有单词构成的有向图中最少存在着一条欧拉路。当然，也可能是欧拉回路。图3是连通的有向图，它没有欧拉回路，但存在欧拉路。图3中T点的入度为2，出度为1，出入度相差为1，H点的出度为2，入度为1，出入度相差为1，Y点的入度为1，出度为1，出入度相等。因此,图3是满足定理2的“除两个结点外，每个结点的入度等于出度。 对于这两个结点，一个结点的出度比入度多1，另一个结点的出度比入度少1”这个充要条件的，故存出度比入度多1，另一个结点的出度比入度少1”这个充要条件的，故存在欧拉路，可以完成接龙。再看图4，其中没有回路，且O点的入度为2,出度为0,出入度之差为2，因此不可能有欧拉路，故不能完成接龙。图论的正确应用大大降低了单词接龙求解的复杂度。3.3 图论在邮政中的应用背景：纵观这些年我国邮政事业，其发展远远落后于经济增长的需求，突出表现在邮政运输能力的薄弱上。邮政运输具有全程全网，联合作业的特点，要求各部分邮路都能做到环环相和，并和邮件处理环节相配合，以最快的速度传递信息载体，所以在组建邮运网这项复杂的系统工程中，不仅要科学地组织邮件运输，还要组织好与邮件运输有紧密联系并相互交叉的处理作业环节。模型建立： 从图论的观点出发，最小载集直接影响网络的运输能力，要想提高邮运的能力，首先应考虑改善最小截集中各条弧的容量，即各段邮路上运能，提高它们的通过能力。另一方面， 一旦最小截集中弧的通过能力被降低，就会使总的输送量减少。下面具体应用“最大流算法”对一局部邮政网进行优化。两个邮局V1和V2发往T1， T2，T3三地的邮件需经V3和V4两个经转局其中“O”中的数字为该局的最大处理能力，弧上所标的权值为该线路的最大运输能力。现欲计算此邮运网的最大运输能力，并对结果进行分析，改善网中的薄弱环节，提高该网的最大运能，如图5。这个问题属于多收点、多发点的网络最大流问题。 首先，虚拟一发点Vs和一收Vt点，将该问题转化为一个收点和发点，如图6所示。其中弧(Vs，V1)的容量取所有以V1为起始点的弧的容量之和(或任一大于这个数的值)，这里应等于20，同样，弧(Vs，V2)的容量取作18+8=26弧(t1，Vt)，(t2，Vt)，(t3，Vt)的容量分别取作12，22，17。同时,由于V3和V4两经转局有理能力的限制,这里将V3点转换为V3和V3两没有任何处理能力的点， 图6图7图8(V3 ，V3)的容量为30，同样转化为V4，得到了一个顶点无容量约束的网络，如图7所示。根据最大流量法，对上图进行标号，找出增广链，并调整，直至无法进行为止。结果如图8。由此可得该网络的最大通过能力为40。从图(58)不难看出，V3局的处理能力还有空余。具体表现在弧(V3，V3)的流量小于容量，V4局的处理能力全部投入使用，并且能力严重不足，邮路(V2，V4),(V4，V2)等还未达到满载，在空载现象，这和我们国家现阶段的情况是不相适应的。要提高整个网络的通信能力消除部分空载现象和瓶颈环节，就必须提高邮路(V1，V3)和(V2，V3)的最大运输能力。提高V4局的处理能力。通过调查分析，V1V3和V2V3间主要依靠干线邮路的火车运邮，V1、V3间的公路情况良好的。同时由于V4的处理能力不足。当V4局的邮件量大时，V局就会发生“堵塞”现象。在物质投入一定的情况下，可在邮运高峰期加开V2V3局之间达的运邮汽车班次，提高这一段邮路的局步运输能力，使V3局的处理能力能够得到进一步利用。V4局的处理能力较差是由于该局的规模过小，机械设备缺乏，邮政工作人员基本上停留于手工作业。针对这种情况，可给该局配置自动分捡机、悬挂输送机，叉车等一系列机械设备，增添一定面积的厂房，并对一部分工作人员进行培训，正确、高效、科学地使用生产设备，以期达到最大工作效率。4、总结：图论是组合数学的一个分支，一般的做法是用边来代表结点之间的联系。凡有二元关系的系统，图论均可提供一种数学模型，因而它在许多科学领域和现实生活中具有越来越重要的作用。本文不仅讨论了两个简单的图论实际应用问题，还具体分析了（1）把高校必修课程之间的领先关系抽象为有向图，把选课问题抽象为在有向图中寻找拓扑有序序列问题，从而成功地解决了高校的选课问题。（2）“单词接龙”的求解问题，运用图论中的欧拉定理建立了数学模型，该算法较之传统的穷举法明显地降低了复杂度。（3）把图论的方法与邮政的实际情况结合起来,通过建立数学模型，将复杂的邮政问题转化为网络结构图，并运用最大流算法，对邮政运输网络进行分析，以达到优化邮政通信网，提高邮政经济效益和社会效益的目的。实例结果表明，图论模型能直观和定量地描述具体问题中各环节之间的关系，使问题皆可得到简化，这为研究解决实际问题提供了一种更直观更简单的新方法.上述几例，可以看出图论的应用范围非常广泛。图论方法在实