图论读书报告

1、图论读书报告在阅读了一些有关图论介绍的文章和书籍后，会发现其中都会提到图论问题的起源，也就是1736年提出的哥尼斯堡七桥间题。在哥尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来。问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后来的欧拉路径和欧拉回路。这项工作使

2、欧拉成为图论及拓扑学的创始人。而且在19世纪关于图论的许多重要结论已得出。但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和传播。许多的图论问题最初都是由一些类似于游戏的问题，例如一笔画，棋盘上棋子的路线，以及一些看起来很简单直观但实际上非常复杂的猜想，例如最终是由计算机证明的四色猜想。这些有趣的问题通过传统的方法往往很难得到解决，在一些具有一定影响力的数学家意识到这些问题的重要意义之后，图论才作为一个理论体系引起了学术界的广泛关注。由此可见，图论发展的第一步实际上是从“游戏”到系统的学科理论的转变。经过一段时间的发展，图论成为组合数学的一个分支，一般的做法是把研究对象抽象化为点

3、，再用边来代表结点之间的联系。这时，一些由一笔画之类的游戏演变而来的图的具体问题，由一些学者进行了系统的解答。得出了哈密顿回路，Dijkstra算法，Floyd算法等理论，这使得后来的实际问题在抽象化之后可以得到优化的解答。图论学科理论得到了长足的发展。在实际运用中,图论模型能直观和定量地描述具体问题中各环节之间的关系,使问题皆可得到简化，这为研究解决实际问题提供了一种更直观更简单的新方法.图论方法在实际生活中的广泛应用，不仅能实现高效、高质解决问题，而且能加强对事件过程的全面控制和管理，降低成本，并进行有效的管理和决策分析。凡有二元关系的系统，只需确定结点和边各代表什么，建立图的模型，运用图

4、论的理论和方法，许多离散的问题都可以得到解决，因而它在许多科学领域和现实生活中具有越来越重要的作用。同时，图论又是应用数学的一个分支，实际上具有很强的实用性。它形象地用一些点以及点与点之间的连线构成的图或网络来表示具体问题。利用图与网络的特点来解决系统中的问题，图论在分析电路网络时的运用，这是它最早应用于工程科学，以后随着科学的发展，图论在解决物理、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理等各个领域的问题时，发挥出越来越大的作用也就是说，图论发展中关键的第二步是抽象，就是把实际问题中的研究对象抽象成点并用边去表示它们之间的联系。这种联系可能是有向的，也可能是无向

5、的。例如，当研究对象没有先后次序之分时，它们的边的关系可能是无向的，例如一些由圆桌问题演变而来的诸如为一些相互认识的人安排座位，为会几国语言的一些人安排座位之类的问题。这些最终都被归结为寻找哈密顿回路的问题，也就是把一个人的两边只能各自坐一个人这一事实，抽象为每个节点通过且只通过一次。而对于安排修课顺序，这样对于对象有先后顺序的问题，则应当采用有向图表示。而对于词语接龙这样的问题，还需要额外考虑到点的度来判断其是否存在欧拉回路。现在主要应用在工程和分配管理两个方面。工程应用方面主要是在线路规划方面，包括交通和物流。我国邮政事业发展远远落后于经济增长的需求,突出表现在邮政运输能力的薄弱上,邮政运

6、输具有全程全网,联合作业的特点,要求各部分邮路都能做到环环相和,并和邮件处理环节相配合,以最快的速度传递信息载体,所以在组建邮运网这项复杂的系统工程中,不仅要科学地组织邮件运输,还要组织好与邮件运输有紧密联系并相互交叉的处理作业环节。保证不会有某条边上的流量超过了两端的点，也就是邮件处理点的处理能力而造成邮件滞留，同时又应该尽量发挥每个邮件处理点的处理能力以提高服务效率。时下比较热门的关于图论的论文涉及了很多的学科，例如图论与PAAM软件结合之后再道路规划方面的运用，而这实际上又可以运用到桥梁的选址中，图论在工程管理方面的运用，图论优化方法在数学建模中的运用，图论在计算机科学和网络拓扑中的应用

7、等。可见，图论发展至此，不仅仅是数学学科的一个分支，它也是众多学科的交叉领域，是如同语言一般存在的工具学科。关于图论的资料介绍中，很多的实际问题都是最终归结于最短路径问题进行解答的，这是图论应用中一个重要部分。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。不管是线路规划还是管理统筹或是网络相关问题，都可以由不同的赋权纳入最短路径问题的范畴之中。例如最短路径算法的选择与实现是通道路线设计的基础，而路线选择中的路径可以是陆路，水路，航空，厂区布局，管路铺设，线路安装，甚至可以是在最短时间内按要求有先

8、后地修满足够的学分，以此来规划学生每个学年所学的科目。在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：（1）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （2）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （3）确定起点终点的最短路径问题：

9、即已知起点和终点，求两结点之间的最短路径。 （4）全局最短路径问题：求图中所有的最短路径。回忆本科期间土木工程的课程，图论在工程管理的课程中有着最为典型的运用。在每个工程中必须写在文件中，计划板墙，甚至要被粉刷在工地围栏上的工程网络图便是图论在工程运用方面的生动例子。利用单，双代号网络图表示工程进程是每个项目经理的基本技能，也是每一学年的工程管理课考试的最后一道大题。相比工程横道图，单代号网络图和双代号网络图可以更加清晰地表现出整个工程的进展过程。它是一种以网络图形来表达计划中各项工作之间相互依赖、相互制约的关系；分析其内在规律，寻求其最优方案的计划管理技术。网络计划技术的基本原理：利用网络图

10、的形式表达一项工程中各项工作的先后顺序及逻辑关系；通过对网络图时间参数的计算，找出关键工作、关键线路；利用优化原理，改善网络计划的初始方案，以选择最优方案；在网络计划的执行过程中进行有效的控制和监督，保证合理地利用资源，力求以最少的消耗获取最佳的经济效益和社会效益.能全面而明确地反映出各项工作之间开展的先后顺序和它们之间的相互制约、相互依赖的关系；可以进行各种时间参数的计算；能在工作繁多、错综复杂的计划中找出影响工程进度的关键工作和关键线路，便于管理者抓住主要矛盾，集中精力确保工期，避免盲目施工；能够从许多可行方案中，选出最优方案；利用网络计划中反映出的各项工作的时间储备，可以更好的调 配人力

11、、物力，以达到降低成本的目的；可以利用计算机进行计算、优化、调整和管理。在网络图的运用中，最重要的元素便是关键线路，这条线路决定了整个工程的耗时，是在工程现场管理进行调整时要时刻注意的。关键线路的线路时间代表整个网络计划的计划总工期，其线路上的工作都称为关键工作；关键线路和关键工作没有时间储备，一旦由于任何原因被延误就会造成整个工期的延长。关键线路是可变的，当管理人员采取某些技术组织措施，缩短关键工作的持续时间就可能使关键线路变为非关键线路。对于关键线路的选择目的实际上是找出对于工程的进行时间起到控制作用的路线并压缩这条线路需要的时间。综上所述，图论的发展经历了从游戏和民间问题，到系统学科，进而成为其他学科研究的辅助工具以及解决和优化实际问题的重要途径的过程。它巧妙地将复杂的实际问题抽象成为点和边的关系并予以解决，仔细回想后会发现这个看似陌生的学科早已被运用在生产生活的方方面面，我们在从小到大的学习过程中，曾经在启蒙的数学书上，在中学电路的学习中，在大学的管理规划的学习中，在数学建模的比赛中无意与它接触。相信随着计算机技