欧拉图的判定方法及其在实际生活中的应用
关键词：欧拉图；判定定理；中国邮路问题算法
The Application of Determination Method of Euler Graph in the Real Life
Abstract: Not only Euler graph has an important role in the ordinary logic, but it also has a relatively wide range of applications in the real life, such as solving Chinese Postman Problem, traveling salesman problem, the problem of rows of seats, criminal investigation logical problem, determine whether a graph is in one stroke and so on. The method for determining Euler graph has two aspects, the first is the determination of Euler graph’s definition, and the second is using judgment theorem to judge. This paper introduces the research background, basic concepts and common decision theorem of Euler graph and gives several practical applications of Euler graph in life.
Key words: Euler Graph; Judgment Theorem; Chinese Postman Problem Algorithm
目 录
摘 要 1
引言 1
1.概述 2
1.1欧拉图的研究现状及研究意义 2
1.2预备知识 3
2.欧拉图的判定方法 3
2.1用欧拉图的定义来判定 4
2.2用定理来判定 4
3.欧拉图在实际生活中的应用 4
3.1一笔画问题 4
3.2 中国邮路问题 5
3.3 中国邮路问题案例应用 6
3.4牛奶配送问题 7
3.5 牛奶配送问题案例分析 7
4.结论 9
参考文献 9
致谢 10
欧拉图的判定方法及其在实际生活中的应用
引言
欧拉图问题是图论中最古老的问题之一，它诞生于十八世纪的欧洲古城哥尼斯堡。普瑞尔河流经这座城市，人们在两岸以及河中间的两个小岛之间建了七座桥，市民们喜欢在这里散步，于是产生了这样一个问题：是否可以找到一种方案，使得人们从自己家里出发，不重复地走遍每一座桥，然后回到家中?这个问题如果用数学语言来描述，就是找出一条回路，使得它不重复地经过每一条边。这便是著名的“哥尼斯七桥问题”，欧拉经过悉心研究，终于在1736年发表了论文《哥尼斯堡的七座桥》，不但成功地证明了“七桥问题”无解，而且找到了对于一般图是否存在这类回路的充要条件。后人为了纪念欧拉这位伟大的数学家，便将这类路称为欧拉图。
1.概述
1.2预备知识
欧拉回路:图 中经过每条边一次并且仅一次的回路称作欧拉回路。
欧拉路径:图 中经过每条边一次并且仅一次的路径称作欧拉路径。
欧拉图:存在欧拉回路的图称为欧拉图。
半欧拉图:存在欧拉路径但不存在欧拉回路的图称为半欧拉图
性质：设 是欧拉图 中的一个简单回路，将 中的边从图 中删去得到一个新的图 ，则 的每一个极大连通子图都有一条欧拉回路。
2.欧拉图的判定方法
欧拉图的判定方法可以从两个方面着手，第一是用欧拉图的定义判定，第二是用定理判定，也就是经过图G的每条边一次且仅一次的路径，称为欧拉路径，同理，满足相同条件的回路，称之为欧拉回路。欧拉图就是具有这种特殊条件的图；即可以延伸定义为各点的度数都是偶数的图必然是无向连通图；