摘 要：图论的优化问题在实际生活中有着广泛的应用.本文讨论了几个典型的图论优化问题，研究解决这些问题的各种算法，并通过计算机软件编程加以实现.

毕业论文关键词：图论，最优化，算法66421

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所示．