浅析图论的实际应用研究

张林晓于丽娜

摘要：本文在学习图论基础知识的基础上，研究图论的实际应用。具体分析了：把高校必修课中的领先关系抽象为有向图中寻找拓扑有序序列问题；将图论的思想与邮递的实际思想相结合；图的着色点问题等。

关键词：图论生活问题实际应用七桥问题

1引言

图论是一门比较古老的学科，是应用数学中的一个重要分支，它存在着广泛的应用背景。与其他的数学分支，如概率论、拓扑学、群论、矩阵论、数分析等有着密切的联系。图论中以图为主要的研究对象，在图形中我们用点来表示对象，两点之间的连线表示对象之间的某种特定的关系。事实上，任何一个包含了二元关系的系统都可以用图论来模拟。而且，图论能把纷杂的信息变的有序、直观、清晰。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要。

图论在自然科学、社会科学等各个领域都有广泛的应用。随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支之一。

2图论的起源与发展

2.1图论的起源[1]

1736年是图论的历史元年。这一年，欧拉（L•Euler）研究了哥尼斯堡七桥问题，并发表了关于图论的首篇文章。欧拉也因此被称为图论之父。当时人们对于这个问题充满了好奇心：一个散步者怎样不重复的走完七座桥，最后回到出发点。“七桥问题”难住了哥尼斯堡城的所有居民。哥尼斯堡城也因“七桥问题”而出了名。1736年，当时著名的瑞士数学家昂哈德·欧拉（LeonhardEuler）仔细地研究了这个问题，他将上述四块陆地与七座桥间的关系用一个抽象图形来描述（见图2），其中A、B、C、D四个陆地分别用四个点来表示，而陆地之间有桥相连者则用连接两个点的连线来表示，这样，上述的哥尼斯堡七桥问题就变成了由点和边所组成的如下问题：试求从图中的任一点出发，不重复的通过每条边一次，最后返回到该点，这样的路线是否存在？这样问题就变得简洁明了，解决起来也更加简单了。由此，七桥问题就转变为图论中的一笔画问题。即能不能不重复的一笔画出图二中的这个图形。欧拉对七桥问题的研究，是拓扑学研究的先声。

图1哥尼斯堡七桥问题

图2欧拉抽象哥尼斯堡七桥问题

2.2图论在解决现实生活问题方面的重要性

起初，图论问题主要用来解决迷宫问题和游戏问题。由于生产管理、军事、交通运输、计算机和通讯网路等方面大量实际问题的出现，大大促进了图论的发展，也就是图论在以上众多方面发挥了重要作用，特别是电子计算机的大量应用，使大规模问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都很复杂的，需要计算机的帮助才有可能进行分析和解决。目前，图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中都有应用。

3图论在现实生活中的具体应用

3.1图论在高校选课中的应用

模型的建立：课程之间领先关系的抽象我们利用图论中有向无回路图的有关知识，把课程之间领先关系转化为有向无回路图中的有向边。其构造有向无回路图的方法是：图中的顶点表示课程，有向边表示课程之间的领先关系；若课程x是课程y的先决条件，则图中出现从顶点x到顶点y的有向边<x，y>。选课问题的抽象借助有向无回路图，我们可把选课问题抽象为在有向无回路图中寻找拓扑有序序列。实行学分制的各个院系，在安排教学计划时，必须考虑到课程之间的领先关系，首先把该专业必修课程之间的依靠关系抽象为有向无回路图，然后从有向无回路图中找到多个拓扑有序序列。通过把课程之间领先关系转化为有向无回路图，进而把选课问题转化为在有向无回路图中寻找拓扑有序序列问题，从而成功地解决了高校学生的选课问题。

3.2中国邮递员问题

1962年，中国数学家管梅谷提出了一个有关邮递员工作的问题：从邮局里取出邮件，接着进行邮件派送，然后再返回邮局。显然，他必须至少经过一次在他投递范围内的每一条街。为了节约时间提高效率，希望能够选择一条尽可能短的路线，这就是中国邮递员问题。如果我们将被投递信件的地点用点来表示，邮递员可供选择的路线用边来表示，每条边上的权表示两个相邻地点的距离，这样就构成一个赋权图G。

显然，中国邮递员问题就是在具有非负权的赋权连通图中找出最小权的环游，这种环游也称为“最优环游”。

3.3图的着色点问题

在历史上，着色问题起源于地图着色。19世纪50年代一个青年学生注意到可以用四种颜色给英格兰的郡地区着色，使得相邻的郡着不同的颜色。在这个基础上，他猜想任何地图都可以用4种颜色着色。他的弟弟是德摩根的学生，他把哥哥的这个想法告诉了德摩根。德摩根对这个问题特别感兴趣并把它公布与众。这就是著名的四色猜想。

4结论

随着计算机网路通信在当今世界的快速发展，图论的应用在很大程度上节约了成本和时间，从以上的案例我们可以看出，图论的应用十分广泛，作用也十分明显。通过上述案例我们得知建立图的模型，正确运用图论的理论和方法，许多离散的问题都可以得到解决。我们在日常学习中应该注重将图论的思想运用到现实生活中去，同时以上的应用和实例也可以进行相应的改善和推广，有利于我们以后的日常生活和工作实践。

参考文献：

[1]李冰.图论的起源和发展[J].大众文艺，2010（9）：34。

[2]黄会芸.图论思想在生活中的运用[J].赤峰学院学报（自然科学版），2009，25（12）：23-24。

[3]耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2004：267。

[4]傅彦.离散数学基础及应用[M].成都：电子科技大学出版社.2000：149-150。

[5]耿素云，屈婉玲，张立昂.离散数学（第三版）[M].北京：清华大学出版社，2010.

[作者简介]张林晓，女，山东协和学院计算机科学与技术专业在读本科生。于丽娜（1987-），指导教师，通讯作者。女，山东烟台，硕士研究生，助教，研究方向：物联网、通信。