欧拉图

欧拉图（Eulerian graph ）是一种特殊的图， 其定义为：给定无向图或有向图G=(V,E)，通过G的每条边一次且仅有一次的回路称为欧拉回路，具有欧拉回路的图称为欧拉图。具有欧拉通路但无欧拉回路的图称为半欧拉图。

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

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

定义

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

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

历史

早期研究

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

后续发展

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

性质

（1） 设 是一个非空连通图，则 是欧拉图当且仅当 中的每个顶点都是偶数度。

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

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

（4）有向图 是欧拉图当且仅当 中每个顶点的入度等于出度。

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

构造方法

费勒里算法

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

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

（2）迹 已取定，选 使：

① 与点 相关联；

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

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

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

希尔霍尔泽算法

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

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

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

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

计算

欧拉迹的数目

有向有拉图

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

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

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

无向欧拉图

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

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

当 且 为奇数时，

，

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

特殊类型

无限欧拉图

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

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

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

（1） 是连通的；

（2） 是可数的；

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

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

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

应用

计算机科学

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

工程学

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

管理学

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