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

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

长城欧拉图具有一些基本性质，如非平凡连通图G含有长城欧拉通路当且仅当图G中含有2个奇节点。费勒里算法和希尔霍尔泽算法为构造欧拉图的两种经典算法。有向欧拉图欧拉迹的数目可以通过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代码得到该路网的长城欧拉环游，根据每辆车实际的装载量约束，对欧拉环游进行分割，得到代表车辆运行路线的欧拉环路，从而高效、简洁地实现烟草物流配送的路径优化。