论文总字数：13325字

摘 要

关键词:图论,Matlab,算法

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 图的基本概念

区别于微积分、解析几何、几何学中所讨论的图形,图论中所讨论的“图”是在客观世界中某些具体事物之间联系的一个数学抽象.例如集合论中二元关系的关系图,在关系图中,人们只关心点之间是否有连线,不考虑点的位置以及连线的长短曲直,这就是图论中的图与几何学中的图最根本的区别^[3].这种数学抽象就是“图”的概念.

2.3 图的种类

在图中,若图的每一条边都是无向的称为无向图；若图的每一条边都是有向的称为有向图；若有一些边是无向的,另一些边是有向的,称该图为混合图.

若图仅由若干孤立的顶点组成,称该图为零图；若图仅由一个孤立顶点构成,称该图为平凡图；若图不含有任何平行边和自回路,称该图为简单图；若图含有任意平行边,称该图为多重图；简单图中,若图中每对顶点间皆有边相连,则称该图为完全图；有个顶点的无向完全图记作；对于无向图G,将G中的每条边用两条和有相同端点的对称边和来代替后得到了一个有向图；对中每条边确定任意一个方向,称该图为顶点的有向完全图；完全图的对称有向图被称为完全有向图,记作.

在无向图中,对于G的每一个节点x,若,则称G为正则的无向图；设为有向图,对于G的每一个节点x,若,则称为平衡有向图,x为它的平衡点；在有向图中,若,则称为正则有向图^[3,4] .

2.4 图论的应用

人们在日常生活中有很多方面要用到图论方法.比如：我国数学家管梅谷教授在1960年首先提出了中国邮递员问题,Dijkstra算法和Floyd算法皆可应用在类似问题的所求最短路径问题当中.Kruskal在1956年设计的求连通加权图的最优数算法,可应用于修筑连接n个城市的铁路,已知城和城之间的铁路造价,设计一个筑路图,使总造价最低^[5].顶点着色问题有着广泛的应用.当我们试图在有冲突的情况下分配资源时,就会自然的产生这个问题.例如,合理安排化学品的存储以避免发生反应.

3 MATLAB的简介

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