摘要：离散数学作为计算机科学与技术和相关专业的必修课程，在数据结构、算法设计与分析、操作系统、编译系统、人工智能、软件工程、网络与分布式计算得到了广泛应用。并且是自动化、化学工程、生物学经济学等各个学科领域数学建模中的重要工具。其中图论是其中重要的一部分，将对其起源到应用进行浅谈。
关键字：离散数学；计算机科学与技术；数据结构；图论
一、图论的起源
哥尼斯堡七桥是古老的数学游戏和趣题研究中最具代表性的一个。普鲁士的古城哥尼斯堡（哲学家康德的故乡，今俄罗斯加里宁格勒）。普瑞格尔河正好从市中心流过，河中心有两座小岛，岛和两岸之间建筑有七座古桥。欧拉发现当地居民有一项消遣活动，就是试图每座桥恰好走过一遍并回到原出发点，但从来没人成功过。首先能想到的证明方法是把走七座桥的走法都列出来，一个一个的试验，但七座桥的所有走法共用7！=5040种，逐一试验将是很大的工作量。欧拉欧拉把两座岛和河两岸抽象成顶点，每一座桥抽象成连接顶点的一条边，假设每座桥都恰好走过一次（如图1）。那么对于A、B、C、D四个顶点中的每一个顶点，需要从某条边进入，同时从另一条边离开。这样问题就简洁明了多了。欧拉想那么多人都失败了是不是这个问题本来就无解。欧拉抓住了问题的本质，最终欧拉考虑了一笔画图像的结构特征：进入和离开顶点的次数是相同的，即每个顶点有多少条进入的边，就有多少条出去的边，也就是说，每个顶点相连的边是成对出现的，即每个顶点的相连边的数量必须是偶数。七桥问题的几何图中，A、B、D三点分别与三条线相连，C点与5条线相连，连线都是奇数条，因此欧拉断定：一笔画出这个图形是不可能的。也就是此题无解。这不仅标志着图论的诞生，更是后来拓扑学的先声。
图1哥尼斯堡七桥问题
二、图论的发展
从十九世纪中叶开始，图论进入了新的发展阶段。这个时期，关于图论出现的大量的问题，其中最典型的是地图染色的四色问题和和“周游世界”发展来的哈密顿问题。四色问题是1892年伦敦大学的毕业生古色列在研究英国地图时发现的，他在看地图边界时的区域划分时同时注意到各区域地图的着色之用的四种颜色。这让他很困惑。于是他写信给仍在学校读书的弟弟，让弟弟向有名的数学家德·摩根请教。但他也没能解决这个问题。于是向自己的好友、著名的数学家哈密顿爵士请教，但直到哈密顿逝世也没有解决这个问题的。后来又有一系列学者对其进行研究，但最终都是错的。最接近的一次是赫伍德利用肯普的方法证明了五色定理，即一张地图可以用五种或者五种以下的颜色进行染色，但仍未能解决问题。最终是1976年6月美国伊利诺斯大学的黑肯和阿佩尔经过四年的艰苦工作，在计算机的帮助下进行了长达1200小时并做了100亿次的判断，终于完成了四色证明的猜想。但有不少数学家并不满足这样，仍在寻求一种简洁明快的书面证明方法。
哈密顿“周游世界”是指用一个正十二面体的20个顶点表示世界上的二十座大城市，要求找一条沿着十二面体的棱通过每个顶点恰好一次的闭路。由于运筹学、计算机科学与编码理论中很多问题都可以转化为哈密顿问题，所以这个问题引起了广泛的关注和研究。
后来1936年，匈牙利著名图论学家柯尼希发表的《有限图和无限图理论》，是图论的第一步专著，它总结了200年的图论成果，是图论重要的里程碑。后来经过五十多年爆炸性发展，图论终于成长为数学科学中独立的学科。
三、图论的应用
结合图论的特点和现实生活中的应用，可以发现图论的使用范围之广，其作为一门学科、一种工具的影响力之大。
（一）网络中的应用
图论的应用中最典型的应用之一是拓扑学。拓扑学事实上是几何学的分支，但又与传统的平面几何、立体几何稍有不同。通常平面几何或立体几何研究的对象是点、线、面之间的位置关系和它们的度量性质，但拓扑对于研究对象的长短、大小、面积、体积等度量和数量关系都是无关的。图论是拓扑学及其重要的工具。比如网络拓扑，它忽略用户终端的大小、型号等，也忽略地理上的距离差异，只从结构上来研究该网络拓扑是否安全可靠。例如星状拓扑结构，我们很难直接从现实连线中看出拓扑的缺陷，但利用图论的知识将画出相关图，以结点代表终端，终端与终端之间的连接用边来表示，整个网络拓扑就抽象成了简单明了的图（如图2），如果我们去除图中的割点x，那么则图的连通性就受到破坏，节点与节点则无法通信。我们可以清楚的看出其中央结点的损坏会影响整个系统的运行。当面对大型且复杂的网络时，利用图可以很方便的对网络进行观察和分析。可以说图论的研究对象就相当于“一维的拓扑学”。
图1拓扑示例
（二）游戏中的应用
图论在游戏中的应用也很多，最经典的比如《一笔画》，这与欧拉图具有相同的特点。从一点出发经过每条边一次且经过所有的点，其原理就是根据欧拉回路的充分必要条件，当且仅当该图是连通图且无奇数顶点。虽然游戏都是经过测试，所有图都能一笔画成。但是根据欧拉图的特性，我们可以找到一些技巧：有且只有两个点的度为一时，则这两个点分别为起点和终点；如果仅存在一个桥，那么必须将一边遍历后才能经过该桥遍历另一边；对于0个“奇数端点”的图形，一笔画的起点可以是图形中的任意一点，它的终点也是这个点等一系列技巧。
（三）生活中的应用
1.中国邮递员
（1）问题引入
“中国邮递员”问题时中国学者管梅谷提出的。在邮递员某一地区投递，每天都从邮局出发，走遍该地区所有街道再返回邮局，那么他将如何安排送信路线使所走总路程最短。如果所走线路能构成欧拉回路，那么我们可知以邮局为起点，按照一笔画原则我们怎么走都是距离相等的。当构不成欧拉回路时，问题就不好解决了。我们可以利用图论知识将线路抽象，将投递地点抽象为点，路线用边来表示，路线的长度用权来表示，那么只需要找到一个权的和最少且能遍历所有投递点的线路即可。
（2）问题延展
引入权的概念后，那么图的作用就更大了。比如对一个旅游景点的旅游路线进行规划，怎样让顾客在走最少的路的同时观赏全部的景色，通过图论抽象，可以方便的进行规划。另外经过权还可以进行交通流量的判断。如果各个道路的最大流量是大致了解的，通过将该数量抽象成权，将道路抽象成边，那么我们就可以方便的看出道路是否畅通，可以采取分流或者扩宽路线的方式来处理。
2.排座问题
有7人聚餐，a会讲汉语和英语；b会讲英语和韩语；c会讲英语和意大利语；d会讲法语、俄语和意大利语；e会讲俄语和韩语；f会讲汉语；g会讲法语和汉语。试问这7个人应如何排座位（圆桌），才能使每个人和他身边的人交谈?
图1图2
我们将每个人抽象成结点，会相同语言的两种人建立关系，用边来表
示这种关系，那么就构成了下图（图3）。因为要求每个人相邻的人都能交流，所以当以一个人为起点时最终会绕回这个人。我们只需要找出一条能通过每一个结点且仅一次的路径，即找出一条哈密顿回路。从图（图4）中可知按照a、f、g、d、e、b、c、a路径构成的哈密顿回路可以解决该问题。
参考文献：
[1]王丽丽.图论的历史发展研究[D].山东大学，2012：8～12.
[2]屈婉玲，耿素云，张立昂。离散数学（第三版）.北京：清华大学出版社，2013：152～155
[作者简介]王衍龙，男，山东协和学院计算机科学与技术专业在读本科生。岳秀明（指导教师，通信作者），女，硕士研究生，信号与信息处理专业，研究方向：物联网技术应用。
论文作者:王衍龙,岳秀明
论文发表刊物:《基层建设》2019年第14期
论文发表时间:2019/7/26
标签：图论论文; 哈密论文; 顶点论文; 拓扑论文; 欧拉论文; 抽象论文; 都是论文; 《基层建设》2019年第14期论文;