欧拉迹

Euler 迹关心的是边资源是否全部恰好消费一次，顶点只是边之间的转接站。于是允许多次回到同一顶点，甚至必须如此；真正不能重复的是边。闭迹把每次进入都与离开配对，开放迹只在两端留下不平衡。

一个简单环本身就是欧拉回路。路径图只有两个端点为奇度，故有从一端到另一端的欧拉迹。两个互不相交的环虽所有顶点度数都为偶数，却不能由一条迹覆盖，说明连通条件不可省。欧拉迹允许重复顶点但不能重复边，与要求访问每个顶点一次的Hamilton 路公理库Hamilton 路与 Hamilton 圈Hamiltonian path · Hamiltonian cycle恰好一次访问图中每个顶点的路径，以及首尾相接的这种圈。不同。对有向图应改用入度、出度和平衡或可达条件。

“8”字图由两个圈共享一个顶点组成，所有顶点度数为偶数，沿第一个圈回到交点后再走第二个圈即可得到 Euler 回路。树若有超过一条边，叶子至少两个且常常更多；只有恰有两个奇度顶点的路径树存在 Euler 迹，一般分叉树不存在。把边序列反转仍是合法 Euler 迹，但从中循环移位只对闭回路有意义。

Euler 判定公理库Euler 道判定Euler trail criterion · Eulerian trail theorem有限无向图存在遍历每条边恰一次的道路，当且仅当非孤立部分连通且奇度顶点数为零或二。给出存在性，迹与回路公理库路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。提供形式语言，在图公理库有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。中，构造算法把边逐条删去并拼接闭回路。DNA 片段组装中的 de Bruijn 图、道路巡检和拼接字符串都把“每条边一次”作为模型；若目标改成每个顶点一次，便转向性质完全不同的Hamilton 问题公理库Hamilton 路与 Hamilton 圈Hamiltonian path · Hamiltonian cycle恰好一次访问图中每个顶点的路径，以及首尾相接的这种圈。。