图论读书报告

在阅读了一些有关图论介绍的文章和书籍后，会发现其中都会提到图论问题的起源，也就是1736年提出的哥尼斯堡七桥间题。在哥尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来。问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后来的欧拉路径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。而且在19世纪关于图论的许多重要结论已得出。但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和传播。许多的图论问题最初都是由一些类似于游戏的问题，例如一笔画，棋盘上棋子的路线，以及一些看起来很简单直观但实际上非常复杂的猜想，例如最终是由计算机证明的四色猜想。这些有趣的问题通过传统的方法往往很难得到解决，在一些具有一定影响力的数学家意识到这些问题的重要意义之后，图论才作为一个理论体系引起了学术界的广泛关注。由此可见，图论发展的第一步实际上是从“游戏”到系统的学科理论的转变。

经过一段时间的发展，图论成为组合数学的一个分支，一般的做法是把研究对象抽象化为点，再用边来代表结点之间的联系。这时，一些由一笔画之类的游戏演变而来的图的具体问题，由一些学者进行了系统的解答。得出了哈密顿回路，Dijkstra算法，Floyd算法等理论，这使得后来的实际问题在抽象化之后可以得到优化的解答。图论学科理论得到了长足的发展。

在实际运用中,图论模型能直观和定量地描述具体问题中各环节之间的关系,使问题皆可得到简化，这为研究解决实际问题提供了一种更直观更简单的新方法.图论方法在实际生活中的广泛应用，不仅能实现高效、高质解决问题，而且能加强对事件过程的全面控制和管理，降低成本，并进行有效的管理和决策分析。凡有二元关系的系统，只需确定结点和边各代表什么，建立图的模型，运用图论的理论和方法，许多离散的问题都可以得到解决，因而它在许多科学领域和现实生活中具有越来越重要的作用。同时，图论又是应用数学的一个分支，实际上具有很强的实用性。它形象地用一些点以及点与点之间的连线构成的图或网络来表示具体问题。利用图与网络的特点来解决系统中的问题，图论在分析电路网络时的运用，这是它最早应用于工程科学，以后随着科学的发展，图论在解决物理、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理等各个领域的问题时，发挥出越来越大的作用．也就是说，图论发展中关键的第二步是抽象，就是把实际问题中的研究对象抽象成点并用边去表示它们之间的联系。这种联系可能是有向的，也可能是无向的。例如，当研究对象没有先后次序之分时，它们的边的关系可能是无向的，例如一些由圆桌问题演变而来的诸如为一些相互认识的人安排座位，为会几国语言的一些人安排座位之类的问题。这些最终都被归结为寻找哈密顿回路的问题，也就是把一个人的两边只能各自坐一个人这一事实，抽象为每个节点通过且只通过一次。而对于安排修课顺序，这样对于对象有先后顺序的问题，则应当采用有向图表示。而对于词语接龙这样的问题，还需要额外考虑到点的度来判断其是否存在欧拉回路。

现在主要应用在工程和分配管理两个方面。工程应用方面主要是在线路规划方面，包括交通和物流。我国邮政事业发展远远落后于经济增长的需求,突出表现在邮政运输能力的薄弱上,邮政运输具有全程全网,联合作业的特点,要求各部分邮路都能做到环环相和,并和邮件处理环节相配合,以最快的速度传递信息载体,所以在组建邮运网这项复杂的系统工程中,不仅要科学地组织邮件运输,还要组织好与邮件运输有紧密联系并相互交叉的处理作业环节。保证不会有某条边上的流量超过了两端的点，也就是邮件处理点的处理能力而造成邮件滞留，同时又应该尽量发挥每个邮件处理点的处理能力以提高服务效率。

时下比较热门的关于图论的论文涉及了很多的学科，例如图论与PAAM软件结合之后再道路规划方面的运用，而这实际上又可以运用到桥梁的选址中，图论在工程管理方面的运用，图论优化方法在数学建模中的运用，图论在计算机科学和网络拓扑中的应用等。可见，图论发展至此，不仅仅是数学学科的一个分支，它也是众多学科的交叉领域，是如同语言一般存在的工具学科。

关于图论的资料介绍中，很多的实际问题都是最终归结于最短路径问题进行解答的，这是图论应用中一个重要部分。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。不管是线路规划还是管理统筹或是网络相关问题，都可以由不同的赋权纳入最短路径问题的范畴之中。例如最短路径算法的选择与实现是通道路线设计的基础，而路线选择中的路径可以是陆路，水路，航空，厂区布局，管路铺设，线路安装，甚至可以是在最短时间内按要求有先后地修满足够的学分，以此来规划学生每个学年所学的科目。在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：

（1）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

（2）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

（3）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

（4）全局最短路径问题：求图中所有的最短路径。

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

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

在网络图的运用中，最重要的元素便是关键线路，这条线路决定了整个工程的耗时，是在工程现场管理进行调整时要时刻注意的。关键线路的线路时间代表整个网络计划的计划总工期，其线路上的工作都称为关键工作；关键线路和关键工作没有时间储备，一旦由于任何原因被延误就会造成整个工期的延长。关键线路是可变的，当管理人员采取某些技术组织措施，缩短关键工作的持续时间就可能使关键线路变为非关键线路。对于关键线路的选择目的实际上是找出对于工程的进行时间起到控制作用的路线并压缩这条线路需要的时间。

综上所述，图论的发展经历了从游戏和民间问题，到系统学科，进而成为其他学科研究的辅助工具以及解决和优化实际问题的重要途径的过程。它巧妙地将复杂的实际问题抽象成为点和边的关系并予以解决，仔细回想后会发现这个看似陌生的学科早已被运用在生产生活的方方面面，我们在从小到大的学习过程中，曾经在启蒙的数学书上，在中学电路的学习中，在大学的管理规划的学习中，在数学建模的比赛中无意与它接触。相信随着计算机技术的发展，图论学科还会有更加长足的发展，并在以后的生产生活中发挥更大的作用。

参考书籍及文章：

[1] 运筹学教材编写组·运筹学·清华大学出版社, 1990

[2]卜月华 图论及其应用 南京：东南大学出版社，2000

[3]戴文舟. 交通网络中最短路径算法的研究 [D ]. 重庆大学硕士学位论文 ,2004.

[4]殷剑宏 ,吴开亚.图论及其算法M. 中国科学技术出版社.

第二篇：图论读书报告

最短路径问题

图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

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

最短路径问题是图论解决的典型实际问题之一，可用来解决厂区布局、管路铺设、线路安装等实际问题。在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：

（1）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

（2）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

（3）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

（4）全局最短路径问题：求图中所有的最短路径。

一、相关定义

1.1图

一集元素及它们之间的某种关系称为图。具体地说，图是一个二元组（V，E），其中集合V称为顶点集，集合E是V中元素组成的某些无序对的集合，称为边集。

例：给定G=(V,E)，其中

 

这便定义出一个图。

1.2赋权图

对图G的每条边e，赋以一个实数w(e)，称为边e的权。每个边都赋有权的图称为赋权图。权在不同的问题中会有不同的含义。例如交通网络中，权可能表示运费、里程或道路的造价等。

1.3最短路径问题

给定赋权图G及G中两点u, v，求u到v的具有最小权的路（称为u到v的最短路）。注：赋权图中路的权也称为路的长，最短(u，v)路的长也称为u，v间的距离，记为d(u，v)。最短路径问题是图论中的一个基本问题。在赋权图中，每条边都有一个数值——权（代表其长度、成本、时间等），找出两节点之间总权和最小的路径就是最短路径问题。最短路径算法包括指定顶点对之间的最短路径算法和所有顶点间的最短路径算法，前者对于运输的合理化具有重要理论意义，而后者的意义在于选择合理的中转中心，使得总的费用最少。最短路问题是一个优化问题，属于网络优化和组合优化的范畴。在图论中最典型的两种求最短路径算法分别是Dijkstra算法和Floyd算法，其中Dijkstra算法适用于前者，而Floyd算法适用于后者。

二、Dijkstra算法

2.1  Dijkstra算法

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

2.2  Dijkstra算法思想

Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2.3  Dijkstra算法具体步骤　　

以下面的例子说明

如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。

             

算法执行步骤如下表：

三、Floyd算法

3.1 Floyd算法的基本思想

全部顶点间最短路径算法具有代表性的是1962年由福劳德（Floyd）提出的算法。他的主要思想是从代表任意2个顶点v_i到v_j的距离的带权邻接矩阵开始，每次插入一个顶点v_k，然后将v_i到v_j间的已知最短路径与插入顶点v_k作为中间顶点（一条路径中除始点和终点外的其他顶点）时可能产生的v_i到v_j路径距离比较，取较小值以得到新的距离矩阵，如此循环迭代下去，依次构造出n个矩阵D⁽¹⁾，D⁽²⁾，…，D⁽ⁿ⁾，当所有的顶点均作为任意2个矩阵v_i到v_j中间顶点时得到的最后的带权邻接矩阵D⁽ⁿ⁾就反映了所有顶点对之间的最短距离信息，成为图G的距离矩阵。最后对G中各行元素求和值并比较大小，决定单个或多个最佳的点。

3.2Floyd算法构造距离矩阵的原理

对一个有n个顶点的图G，将顶点用n个整数（从1到n）进行编号。把G的带权邻接矩阵W作为距离的初值，即D⁽⁰⁾=(d_ij⁽⁰⁾)_{n x m}=W。

第一步构造D⁽¹⁾=(d_ij⁽¹⁾)_{n x m} ，其中d_ij⁽¹⁾=min{ d_ij⁽⁰⁾，d_i1⁽⁰⁾+d_1j⁽⁰⁾ }是从v_i到v_j的只允许以v₁作为中间点的路径中最短路长度。

第二步构造D⁽²⁾=(d_ij⁽²⁾)_{n x m} ，其中d_ij⁽²⁾=min{ d_ij⁽¹⁾，d_i2⁽¹⁾+d_2j⁽¹⁾ }是从v_i到v_j的只允许以v₁ 、v₂作为中间点的路径中最短路长度。

第n步构造D⁽ⁿ⁾=(d_ij⁽ⁿ⁾)_{n x m} ，其中d_ij⁽ⁿ⁾=min{ d_ij⁽ⁿ⁾，d_in⁽ⁿ⁾+d_nj⁽ⁿ⁾ }是从v_i到v_j的只允许以v₁、v₂、…、v_n作为中间点的路径中最短路长度，即是从v_i到v_j中间可插入任何顶点的路径中最短路的长度，因此D⁽ⁿ⁾即是距离矩阵。

3.3Floyd算法具体步骤

以下面的例子说明

某城市考虑在开发区建立垃圾中转站。在垃圾站的选址问题中，点表示可供选址的垃圾站，而其间的连线表示运输费用，其需求点之间运费如图所示（英文字母为可选垃圾站点，数字为相邻站点之间的运费）。在垃圾中转站的选址中，要求该中转站到其他站点的距离最短，即运输费用最少，这里通过运用最短路径Floyd算法可以求出该网点布局的最佳中转站。                         

首先，确定矩阵D ⁽⁰⁾其中若顶点v _i（编号i）到v _j（编号j）有边相连，则d _ij ⁽⁰⁾等于该边边权，否则d _ij ⁽⁰⁾= 而d _ii ⁽⁰⁾=0。由图1写出其初值带权邻接矩阵D ⁽⁰⁾：

然后，对k=1，2，3，…，n依次利用算法原理中第n步递归公式，由已知的D^n-1各元素确定Dⁿ的各元素值。插入顶点a后D⁽¹⁾的各元素和相应的最短路径因为对称性，D⁽¹⁾的第一行元素和第一列元素与D⁽⁰⁾相同，D⁽¹⁾的主对角线上的元素均为0，所以只需计算其余6个元素的值：

由此可知，

依次插入b，c，d，e，可得不断更新的距离矩阵：

最终求得距离矩阵D⁽⁵⁾的各元素值就是相应顶点间的最短路径。

最后，计算第i行各元素值之和C(v_i)即为v_i 到其他各点的运费的总和。由计算可知，a到其他点的费用和为C(a)=33，同理C(b)=27，C(c)=18，C(d)=21，C(e)=33，比较可知c到其他各点的费用最小（若有最小总费用相等情形，可作为备选点）。因此本例就经济因素而言，c点为垃圾中转站是最优的。

四、结论

图论在我们生活中的应用比比皆是，解决了很多实际问题。这两种方法不仅适用于此处，还能够方便解决实际应用中最短路径的其他问题，在我们生活中有着重要的价值。