摘 要:图论在生产实践和实际生活中都有广泛的应用。本文研究几类典型的图论问题,探讨解决这些问题的常用算法,通过Matlab软件编程加以实现,并给出一些应用实例。

毕业论文关键词:图论,Matlab,算法74171

Abstract：Graph theory is increasingly used in practical production and real life。In this thesis some sorts of typical problem to be studied,and their solving methods were outlined and discussed。In software design,graph theory algorithm had been completed,and give some practical examples。

Keywords：graph theory,matlab,algorithm 

目   录

1 引言  4

2 图论的基本知识  4

2。1 图论的起源和发展 4

  2。2 图的基本概念 4

  2。3 图的种类 5

  2。4 图论的应用 5

3 MATLAB的简介 5

3。1 MATLAB的产生和发展  5

3。2 MATLAB语言的特点  6

4 典型图论问题的MATLAB求解 6

  4。1 最短路径问题 6

  4。1。1 Dijkstra算法 6

  4。1。2 Floyd算法 9

  4。2 最小生成树问题 15

  4。3 顶点着色问题 19

结论  23

参考文献  24

致谢  25

1  引言

欧拉对哥尼斯堡“七桥问题”的研究是图论研究的开端。欧拉仅用一步就证明了这个问题是无解的,并且令这个问题包含的意义更加深远,给出了对于给定的一个图如何判定是否能够遍历的方法。这也就是后来人们所了解的欧拉通路、欧拉回路以及欧拉图问题。欧拉成为了图论学的创始人。图论所研究的内容非常的广泛,如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等等[1]。

由于计算机的快速普及,图论得到了飞速的发展。虽然图论研究的范围仅限于点和线,但其应用领域相当广阔,不仅局限于数学和计算机学科,同时涉及了社会学、交通管理、电信领域,而这些学科的发展又在很大程度上促进了图论的发展。

本文对图论和Matlab进行了简单的介绍,然后基于Matlab软件,针对图论的典型问题,如最短路径问题、最小生成树问题和顶点着色问题建立数学模型并进行算法描述,根据算法利用Matlab软件进行编程,从而解决问题。

2  图论的基本知识

2。1图论的起源和发展

从图论诞生到现在已经过了两百多年,但是人们对它的关注从未减弱。图论起源于一个实际问题——哥尼斯堡“七桥问题”。1736年,瑞典著名的数学家欧拉发表论文《哥尼斯堡七座桥》论述了不重复通过七座桥的路线不存在,图论由此诞生。人们把他的那篇论文作为图论历史上第一篇论文。

19世纪中叶到1936年期间涌现了大量图论问题,如四色问题和哈密顿问题。同时图论作为工具被用来解决其他领域的一些问题成果。最具代表性的工作包括在1847年和1857年基尔霍夫和凯利分别用树的概念去研究电网方程组问题和有机化合物的分子结构问题。1936年第一本图论专著《有限图与无限图的理论》由康尼格编著而成。在这之后图论成为了数学的一个新分支。

由于生产管理、军事、交通运输、计算机和通讯网络等方面的许多离散性问题的出现,在1936年以后图论的发展被极大的促进了。70年代以后,由于大型电子计算机的出现,大规模问题的求解成为可能。此后,图的理论及其在几乎全部学科领域中各个方面的应用和研究都得到了“爆发性发展”[2] 。

2。2  图的基本概念