【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《浅谈欧拉图、哈密顿图的起源与应用》，欢迎阅读！
浅谈欧拉图、哈密顿图的起源与应用
摘要：图论是计算机科学中最重要的一部分，欧拉图和哈密顿图在图论研究中具有重要的地位，是图论中不可或缺的一部分，它两类的研究已经应用到各种领域，为人们节约了大量的时间。合理利用欧拉图和哈密顿图，不仅可以将复杂的问题简单化，还能提高工作效率。因此，很多学者喜欢研究欧拉图和哈密顿图，并在其中有不少成就。
关键词：欧拉图、哈密顿图、起源、应用 1 欧拉图的起源
18世纪，普鲁土的哥尼斯堡，有一条贯穿全城的普雷格尔河，河中有两个岛屿，有七座桥将两岸与岛屿及岛屿之间连接，当地人们热衷于一个难题：一个散步者怎样不重复地走完七桥，最后回到出发点这就是哥尼斯堡七桥问题。试验者很多，但都没成功。为了寻找客案 瑞士数学家昂哈德。欧拉（Leonhard Euler）对此问题进行研究。他将4块陆地抽象成4个顶点A。B。C，D。若两块陆地之间有桥，就在代表它们的顶点之间连边。
哥尼斯堡七桥问题就是要寻找经过图中每条边一次且仅一次的简单回路。欧拉在1736年的论文中指出，这样的回路是不存在的，从而得出哥尼斯保七桥问题无解的结论这就是欧拉回路的来源。
欧拉图的判定方法：图中有一点，由该点出发经过每条边一次并且仅一次的通路称作欧拉通路；图中有一点，由该点出发经过每条边一次且仅一次的回路称作欧拉回路，具有欧拉回路的图称为欧拉图。只有欧拉通路而无欧拉回路的图不是欧拉图。
2 哈密顿图的起源
哈密尔顿（Hamilton）是爱尔兰的一位数学家和天文学家。他的一生是多姿多彩的，自从哈密尔顿发现“四元数”之后，他又发现了另外一种他命名为“The Icosian Calculus”的代数系统，这系统有加法和乘法的运算子（operators），可是乘法不满足交换律（Commutative law）。
他发现这代数系统是和正则12面体是有关系的。于是，哈密尔顿于1859年提出了所谓的“周游世界游戏”用一个正十二面体的20个顶点表示全世界的20个大城市。
一个人要从某一个城市出发，经过每个城市恰好一次，然后回到出发点，问这样的旅行路线是否存在?这个游戏曾风靡一时。运用拓扑的思想，将这个正十二面体“拉平”就会得到一个与它同构的平面图。这样，这个游戏就转化为：要求沿着正十二面体的棱，怎样跑遍正则多面体上的所有顶点，而最后又能回到起点的问题。
哈密顿定理：任选图中一点，从该点出发，经过每个顶点一次且仅一次的通路称作哈密顿通路；经过每个顶点一次且仅一次的回路称作哈密顿回路；若图中存在哈密顿回路，则称G为哈密顿图。 3 欧拉图和哈密顿图的实际应用 3.1 “一笔画”问题
图1 邮递员问题示例
一笔画，顾名思义就是从图的一个点出发，连续地沿着图的每条边恰好画一次，在画图过程中，笔是不能离开纸的，一笔画问题是数学图论中的一个重要内
容，在生活中也有着重要的应用.比如洒水车进行清洗马路的工作，怎样设计一种科学的走法，使它既能完成洒水任务，又可以不重复地走过每条街道呢?在解决这个问题的过程中，就可以用一笔画问题解决。既然可以将一笔画问题与实际生活相结合，如果我们想顺利用一笔画问题分析实际生活中的问题，我们应该注意以下几点：
（1）一笔画时，如果图中都为偶点，那么可以把任一偶点作为起点，最后定是以这个点为终点画完此图；
（2）如果图中只有两个奇点（其余都为偶点）么必须把一个奇点作为起点，最后一定是以另一个奇点为终点画完此图。 3.2 邮递员投送信件问题
一个邮递员投送信件的街道如图1所示，图上数字表示各段街道的千米
数．他从邮局出发，经过要分发邮件的所有街道，送完邮件后回到邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。
走什么样的路线最合理，简单的说是走哪一条线路，使邮递员能走遍所有的街道，并且路程最短。邮递员从邮局出发，最终回到邮局。但是图中有8个奇点，显然邮递员要走遍所有街道而又不走重复的路是不可能的．要使邮递员从邮局出发，仍回到邮局，必须使8个奇点都变成偶点，就是要考虑应在哪些街道上重复走，也就是相当于在图上添哪些线段，能使奇点变成偶点．如果有不同的添法，就还要考虑哪一种添法能使总路程最短．为使8个奇点变成偶点，我们用如下图2的4种方法走重复的路线
图2邮递员问题示例解法 3.3 座位安排问题
今有a，b，c，d，e，f，g共有7个人。已知下列事实：a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲日语和汉语；e会讲德语和意大利语；f会讲法语、日语和俄语；g会讲法语和德语。试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？
以7个人a，b，c，d，e，f，g作为图的顶点，如果每两个人都会说同一种语言，则对应两个顶点之间有边。a，b，c都会讲英语，a会语种最少，因此a的两边是b，c。b，d会讲汉语，b和d相邻。d和f会讲日语，d，f相邻。f，g都会讲法语。f，g相邻。g，e都会讲德语，g，e相邻。e和c都会意大利语，e，c相邻，最后，c和a都会英语，组成一个闭合的哈密顿图。 4 结语
图论可以用来分析事物之间的联系，可以说有最一般的意义，因为它是基于集合论的。它交叉地运用了拓扑学、群论和数论知识，并且图论在物理系、化学、生物学、工程科学、管理科学、计算机科学等各个领域都有广泛的应用。随着科学技术的蓬勃发展，它的应用还将渗透到自然科学，社会科学等领域，并对我们解决日常生活问题具有重要意义。 参考文献：
[1]屈婉玲、耿素云、张立昂.离散数学（第三版）[M].北京：清华大学出版社.，2007.
[2]张君.从七桥问题想到的用欧拉图来解决计算机应用问题[J].内蒙古民族大学学报，2012，18（02）：11-12。
[4]孙景昊.时变中国邮路问题的整数规划模型及算法研究[D].大连理工大学，
2012。
[5]伍庆成.论欧拉图、哈密顿图的判定及应用[J].中国高新技术企业，2007（07）：207-208。
[6]周炳生，高向阳。哈密顿图和欧拉图的一种判别方法[J].广西科学院学报，2006（01）：1-5。
[作者简介]王海燕，女，山东协和学院计算机科学与技术专业在读本科生。王浩，男，山东协和学院计算机科学与技术专业在读本科生。岳秀明（指导教师，通信作者），女，硕士研究生，信号与信息处理专业，研究方向：物联网技术应用。
本文来源：https://www.wddqxz.cn/abcad0b2f58a6529647d27284b73f242336c31ba.html
2023-01-11
