论文总字数：11776字

摘 要

关键词：图论，最优化，算法

Abstract: Graph theory of optimization has been widely used in the real life. In this paper, we discuss several typical optimization problem of graph theory, then we study the various algorithms to solve these problems. At the last, we use the computer software programming to implement it.

Keywords: graph theory,optimization,algorithm

目 录

1 引言 4

2 相关知识 4

2.1 图的简介 4

2.2 有向图与无向图 4

2.3 树的定义及其性质 5

3 典型图论优化问题的解法 5

3.1 最短路径问题 5

3.2 最小生成树问题 9

3.3 TSP问题 12

3.4 最大流问题 15

3.5 关键路径问题 17

结论 20

参考文献 21

致谢 22

1 引言

图论是数学的一个分支，它以图为研究对象^[1]。图论的发展推进了科学文明的进步，解决了生活中很多应用问题.图论在人们生活中被广泛的运用与接触，优化问题^[1,2]也大量存在于人们日常生活之中.例如经常会遇到的旅游线路最短路线问题^[3]，电网或管道网的最少材料问题^[4]，物流网络优化问题^[5]等。本文主要对图论的优化问题进行研究，将图论基础知识、图论典型问题以及相应的简单实例完美结合在一起.

本文基于数学运算软件，对典型图论问题如最短路径问题，最小生成树问题，TSP问题，最大流问题以及关键路径问题^[6]建立数学模型并进行算法描述，并根据算法利用计算机软件，对相应的实例进行代码编写，从而解决问题.

为了使本文能归纳到比较全面的数学建模知识，同时体会对许多问题求解的特别方法和技巧，在文章中，对于不同问题的求解，根据软件的方便程度，会采用不同的软件进行求解.

2 相关知识

2.1 图的概念

图论所研究的对象就是在自然界和人类社会中所包含的二元关系的系统．就是将一个系统抽象为点和边所构成的一个图，如图1所示．用点表示事物，用边表示事物之间的关系，再根据图的性质进行分析．

设点集，边集，如果对任一边，V中一个点对和他们对应，则称由V和E组成的集体为一个图，记为G=（V, E）．点和称为边的端点，或与边彼此关联，和彼此相邻．如果两边和关联相同的点，则和称为相邻边.显而易见，关联是指不同元素之间的关系，相邻是指相同元素之间的关系^[1]．

2.2 有向图与无向图

一个图的所有边都具有方向，即一个图的所有边都是由有向边构成的，这种图就叫做有向图，如图2所示．典型的例子就是单向通行的公路网，将这种公路网的交叉点、道路分别对应图的各个顶点和边，然后，若把单向通行的路用有向边表示，把往返通行的路用方向相反的并联有向边表示，就得到公路的有向图．同样的若一图仅由无向边构成，则这种图叫做无向图，如图3所示．

2.3 树的定义及其性质

连通图G的不包含任何回路的最大子图T叫做图G的树，如图4所示．若树T就是G图本身，则G图就是一棵树．属于树T的边叫做“树枝”，不属于树T的边叫做“弦”．树T中线度为1的顶点成为树叶．

树的性质:

（1）一棵树每两点之间都是有且只有一条路径．一棵有N个点的树就会有N-1条边，即为连接N个点所需要的最少边数．所以若删除树中的任意一条边，树就会不连通．

（2）在一棵树中加入任意一条边，就会形成有且仅有一个环的图．这是因为这条边连接的两个点中有且仅有一条边，这条边和新加进去的边连接在一起就会成为一个环．如果把一个连通图中的多余边全部删除，那么所构成的树就叫做这个图的生成树．

（3）若需在树中加入一个点，则就要加入一条将这个点和原有的点相连接的边．这条边不会使这棵树形成一个环或多余的路．所以按上述方法每次加进一个点，就能构成一棵树．

（4）一棵树既可以是有向的也可以是无向的．

3 典型图论问题的解法

3.1 最短路径问题

最短路径问题是图论研究的一个经典问题，旨在寻找图中两结点之间的最短路径.主要特点是以起始点为中心向外层层展开，直到展开到终点为止.

下面介绍一种求最短路的常见算法，Dijkstra算法^[1].设P(u,v)是加权图G中从u到v的路径,该路径上的权值之和称为该路径的权,记为W(P).从u到v的路径中权最小者称为u到v的最短路径.Dijkstra算法就是从点出发，逐步地向外探寻最短路.算法执行过程中，与每一个点对应，记录一个数，它表示点到该点的最短路的权（记为P标号），或表示点到该点的最短路的权的上界（记为T标号），算法的每一步就是去修改T标号，并且把记为T标号的点改成记为P标号的点，从而使图中P标号的顶点数多一个，至多经过p-1步，就可以求出点到各点的最短路径.

要求点到其他各点的最短路径，各边的权表示路径长度，如图5所示．

解决问题步骤如下，

（1）与点相邻的顶点有，两点，最接近于点，连接，令．

（2）与S={，}相邻的点有，，，且

连接 ．

（3）与S={，，}相邻的点有，，，且

连接、．

剩余内容已隐藏，请支付后下载全文，论文总字数：11776字