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

关键词:图论,Matlab,算法

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

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

目录

摘要

Abstract

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