欧拉图

具有欧拉回路的图

欧拉图

欧拉图（Eulerian graph[1]）是一种特殊的图，[12]其定义为：给定图G=(V,E)，通过G的每条边一次且仅有一次的回路称为欧拉回路，具有欧拉回路的图称为欧拉图。[13][5]欧拉图的产生源自18世纪的哥尼斯堡七桥问题。[5]1736年，欧拉（Leonhard Euler）在论文《哥尼斯堡七桥问题》中证明了该问题无解，这篇论文被认为是图论的起源，[2]其中涉及到具有特定性质的一种图，后人为了纪念欧拉，称之欧拉图。[12]进入20世纪，各种类型的欧拉图被进一步研究与讨论。1912年，凡勃伦（Veblen）对无向欧拉图给出了“当且仅当不定向连通图是某些循环的不相邻联合时，它才是欧拉图”的结论。1962年，福特（Ford）和富尔克森（Fulkerson）给出了混合图为欧拉图的充分必要条件。[4]同年，中国学者管梅谷首先提出了中国邮递员问题，[5]该问题与欧拉图和最短路径问题有关，可以从图论的角度给出表述，是欧拉图应用于实际的一个典型实例。[13]

欧拉图（Eulerian graph[2]）是一种特殊的图，[13]其定义为：给定图G=(V,E)，通过G的每条边一次且仅有一次的回路称为欧拉回路，具有欧拉回路的图称为欧拉图。[14][6]

欧拉图的产生源自18世纪的哥尼斯堡七桥问题。[6]1736年，欧拉（Leonhard Euler）在论文《哥尼斯堡七桥问题》中证明了该问题无解，这篇论文被认为是图论的起源，[3]其中涉及到具有特定性质的一种图，后人为了纪念欧拉，称之欧拉图。[13]进入20世纪，各种类型的欧拉图被进一步研究与讨论。1912年，凡勃伦（Veblen）对无向欧拉图给出了“当且仅当不定向连通图是某些循环的不相邻联合时，它才是欧拉图”的结论。1962年，福特（Ford）和富尔克森（Fulkerson）给出了混合图为欧拉图的充分必要条件。[5]同年，中国学者管梅谷首先提出了中国邮递员问题，[6]该问题与欧拉图和最短路径问题有关，可以从图论的角度给出表述[注1]，是欧拉图应用于实际的一个典型实例。[14]

欧拉图具有一些基本性质，如非平凡连通图G含有欧拉通路当且仅当图G中含有2个奇节点。[14]费勒里算法和希尔霍尔泽算法为构造欧拉图的两种经典算法。[10][15]有向欧拉图欧拉迹的数目可以通过BEST定理来计算，[16]而对于无向欧拉图，计算过程更为复杂，它是一个#P完全问题。[11]此外，欧拉图在现实世界中应用广泛，如在工程学领域，采用基于欧拉图的挖掘机施工路径规划算法，可以实现挖掘点位置与深度的在线软测量，有效地提升施工效率、节省成本。[8]

定义

欧拉图、欧拉半图：给定无向图（有向图），通过的每条边一次且仅有一次的回路（通路）称为欧拉回路（通路）。具有欧拉回路的图称为欧拉图，[14][6]具有欧拉通路但无欧拉回路的图称为半欧拉图。平凡图为欧拉图，[6]且每个欧拉图必然是连通图。[17]

欧拉环游：图中的一条链（或路），若它通过中的每条边（或弧）恰好一次，则称该链（或路）为欧拉链（或欧拉路），[17]闭的欧拉链称为欧拉环游。[18]

早期研究

欧拉图的产生源自18世纪的哥尼斯堡七桥问题。[6]1736年，瑞士数学家欧拉（Euler）发表了一篇著名论文《哥尼斯堡七桥问题》。文中描述的问题是：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七座桥连接，每逢节假日，有些城市居民进行环城周游，问能否“从某地出发，通过每桥恰好一次，在走遍七桥后又返回到原处”。欧拉指出，从某点出发再回到该点，中间经过的节点总有进入该点的一条边和走出该点的一条边，而且路的起点与终点重合。因此，如果满足条件的回路存在，则途中每个节点的度数必为偶数。哥尼斯堡七桥问题图中4个节点的度数均为奇数，故七桥问题无解。这篇论文被认为是图论的起源，[3]其中涉及到具有特定性质的一种图，后人为了纪念欧拉，称之欧拉图。[13]

欧拉
欧拉

后续发展

后来，欧拉提出了无向图成为欧拉图的必要条件。他还指出这些条件是充分的，但并未提供实际证明。1873年，希尔霍尔泽（Hierholzer）在其遗著中证明了这个充分性。进入20世纪，各种类型的欧拉图被进一步研究与讨论。1912年，凡勃伦（Veblen）对无向欧拉图给出了“当且仅当不定向连通图是某些循环的不相邻联合时，它才是欧拉图”的结论。1962年，福特（Ford）和富尔克森（Fulkerson）给出了混合图为欧拉图的充分必要条件。[5]同年，中国学者管梅谷首先提出了中国邮递员问题，即邮递员从邮局出发经过他投递的每一条街道，然后返回邮局，希望找出一条行走距离最短的路线。[6]这个问题与欧拉图和最短路径有关，可以从图论的角度给出表述[注1]，是欧拉图应用于实际的一个典型实例。[14]

管梅谷
管梅谷

性质

（1） 设是一个没有孤立点的无向连通图，则是欧拉图当且仅当中的每个顶点都是偶数度。[1]

（2）非平凡连通图含有欧拉通路当且仅当图中含有个奇节点。[14]

（3）设图含有一条欧拉通路，、分别为这条欧拉通路的起点与终点，在这条通路上除、外，其余节点都与偶数条边相关联，因此，图中仅、这两个节点是奇节点而其他的节点均是偶节点。[14]

（4）有向图是欧拉图当且仅当是弱连通的且每个顶点的入度等于出度。[6]

（5）有向图有欧拉通路当且仅当是单向连通的且中恰有个奇度顶点，其中一个的入度比出度大，另一个的出度比入度大，而其余顶点的入度都等于出度。[6]

有向欧拉图示例
有向欧拉图示例

费勒里算法

算法：费勒里算法由费勒里（Ferrery）在1921年给出，是一种求欧拉回路的算法。[19]证明某图是欧拉图（或含有欧拉回路），可以借助费勒里算法利用定义在图中寻找一条欧拉回路。具体步骤为：[20]

（1）任取一个顶点，令，。[10]

（2）迹已取定，选使：

①与点相关联；

②除非无奈，选使它不是的割边。[10]

（3）如果选不出，则结束。否则，得到，其中的两个端点分别为点和点，令，转步骤（2）。[10]

分析：在费勒里算法中，每次选择一条边，而选择边时主要是判断这条边是否是割边，而判断一条边是否是割边有多项式时间算法（），所以，对一个欧拉图，费勒里算法的复杂性至多为[注2][10]。

希尔霍尔泽算法

算法：该算法在1873年由德国数学家希尔霍尔泽（Hierholzer）[21]给出，是一种比费勒里算法更快的方法。从任意节点开始并跟随链接，直到返回到节点。如果每个节点的度均为偶数，则在进入一个节点后，将至少有一个链接引出，这样就不会被困在那里。但例外情况是起始节点，因为是从该节点出发的，所以它有奇数个未使用的链接。当再次回到起始节点时，可能会占用它的最后一个链接并陷入困境。因为不会被困在其他地方，因此必须最终回到起始节点。该算法的具体步骤为：[15]

（1）任选一个起始节点。[21]

（2）沿边从一个节点到另一个节点，指导返回起始节点。这样所得的回路不一定包括所有边。[21]

（3）在所得的回路中，若存在一个顶点，它是某边的端点，且该边不在所得的回路中，则从该顶点开始，用还未用过的边寻找另一条路径，直到回到该起点，从而形成另一回路。然后把后面所得的回路拼接到前面已得到的回路中。[21]

有向有拉图

BEST定理：一个有向图中的一条欧拉迹是一条闭生成通道，其中的每一条弧恰出现一次。BEST定理给出了有向欧拉图中欧拉迹的数目。在一个有向欧拉图中，欧拉迹的数目等于：[16]

其中，，是的所有余因子的公共值。[16]

对于任意有特定方向的欧拉图，可以同时使用BEST定理和Matrix-Tree定理计算图中欧拉迹的数目，但使用这种方法遇到的困难在于给定方向中的树突数会变化很大。[11]

无向欧拉图

结论：无向欧拉图的计算是完全的。[11]

特殊情况：1998年，麦凯（McKay）和罗宾逊（Robinson）确定了完全图中欧拉电路数量的近似公式为：[22]

当且为奇数时，

，

对于任何，其中表示随机规则路线在均匀分布下的数学期望。[22]

无限欧拉图

无限图：指顶点个数为无限个的图（边数也可能为无限）。[23]

无限欧拉图：埃尔德（Erdős）及其合作者给出了欧拉著名结果的一个无限扩展，该结果提供了一个充分且必要的条件，即一个循环通过所有边恰好一次。[12]

一个无限图正好具有一个欧拉线当且仅当：

（1）是连通的；

（2） 是可数的；

（3） 没有顶点的度数为奇数；

（4）如果是一个有限的顶点集合，那么最多有两个无限连通分量；

（5）如果是一个有限的顶点集合，使得在中所有顶点都有偶数度，那么通过从中移除中的边得到的图恰好有一个无限连通分量。[12]

计算机科学

在道路建模技术中存在建模效果不理想的情况，在大尺度道路网建模中缺乏有效的辅助交互技术支持。通过对立交结构进行分析，可以提出一种有效的三维立交结构的欧拉图表达及交互设计方法。基本思想是：首先将道路信息预处理，根据处理后的有效数据构建欧拉图，用来表达道路立交结构的拓扑关系；然后利用欧拉图和道路的结构特性计算得到道路的层级关系；再根据控制点、欧拉图的拓扑信息和道路网格，构建立交结构的三维模型；最终构建辅助信息工具，实现对道路网的交互编辑。[7]

欧拉图数据结构
欧拉图数据结构

工程学

在工程学领域，挖掘机存在施工路径、位置与深度盲目和效率低的问题，采用北斗定位接收机、激光测距仪、陀螺仪等传感器对传统挖掘机进行信息化改造。根据挖掘机施工特点，可采用基于欧拉图的挖掘机施工路径规划算法，将遗传算法、原子搜索优化算法和粒子群算法融合在一起对施工图进行欧拉化处理。根据多传感器信息建立挖掘机三维施工模型，可以实现挖掘点位置与深度的在线软测量，有效地提升施工效率，节省施工成本。[8]

基于GAP的挖掘机施工路径规划算法
基于GAP的挖掘机施工路径规划算法

管理学

烟草商业企业配送环节的线路优化算法一直以来都是烟草物流研究的热点问题。在自建GIS服务的基础之上，以OSM路网文件为底图，利用高德地图API构建基础路网，通过对路网进行分析处理，得到基础欧拉图。再利用Python代码得到该路网的欧拉环游，根据每辆车实际的装载量约束，对欧拉环游进行分割，得到代表车辆运行路线的欧拉环路，从而高效、简洁地实现烟草物流配送的路径优化。[9]

烟草物流
烟草物流

参考资料 23

  1. 参考 1
  2. 参考 2
  3. 参考 3
  4. The Euler Tour and Chinese Postman Problem — Anil Aswani
  6. 参考 6
  7. https://kns-cnki-net-443.webvpn.cauc.edu.cn/kcms2/article/abstract?v=qwZretP9BaHlFQOfijgcyprOT2Sr3Ci2b-bpsEWL3l6m-tOLHgyrtNyvXcz79JGNyEnWnzTxtHHV9wpKB2OpYRVR3VSG4a1boVwHn37akC20HLpbMxcWhDW-Jh6HG7rJQOJpUpWBkRycQ_fO5AfdNg==&uniplatform=NZKPT&language=CHS
  8. https://kns.cnki.net/kcms2/article/abstract?v=qwZretP9BaGzXxxFEzBXmwJ5OBhmf9O9SAtVnYMnDj2vYK2L11BVzzVrQUA_VcKa8nbIuxG0SmWmitnecSF2fIudnO86_Zv5Hi6shOmBCaUj42-JqguP71HIl8_FxHe2hvwtRAJiW4M4oQFMJwjyOw==&uniplatform=NZKPT&language=CHS
  9. https://kns.cnki.net/kcms2/article/abstract?v=qwZretP9BaEJSQ9gPLA9wEahm3J6nDblT-K_iCk2-rVCI3dJ3PTSbxbX3WbKhbgxtlloO-YNTUEtlkJdBcO2qRjlnNp3aDdG1nSGG99yPMhgffTNBHN2UNF1cAM84z8wRy-gqqdwpFv0EtFtlHcqjg==&uniplatform=NZKPT&language=CHS
  10. 参考 10
  11. 参考 11
  12. 参考 12
  13. 参考 13
  14. 参考 14
  15. 参考 15
  16. 参考 16
  17. 参考 17
  18. 参考 18
  19. 参考 19
  20. 参考 20
  21. 参考 21
  22. 参考 22
  23. 参考 23

注释

  1. 中国邮政问题的图论表述：在一个带权图中如何寻找一条回路，要求该回路包含图中每条边至少一次，同时具有最短的长度。
  2. 最快可到O(εv)[14]
广告位：底部（ad-bottom）—— 请到中台「公共区块」编辑此内容