欧拉回路与欧拉路径的算法流程演示

算法流程演示算法流程可能有一些复杂我们通过一个例子来理解算法的执行步骤。例如考虑用 Hierholzer 算法找出下图的欧拉回路。首先进行步骤 1 。从任意节点出发不妨从节点 出发沿着边遍历图删除经过的边直到无法继续前进。假设我们的遍历路径为 此时我们找到了一个包含 的回路。将该回路添加到结果序列中此时的结果序列即为 而图也变成了下面的样子。接下来进行步骤 2 。检查刚刚添加到结果序列中的节点节点 、 、 。我们发现节点 还存在未被遍历的边 和 因此我们从节点 出发重复步骤 1。假设我们的遍历路径为 此时我们找到了一个包含 的回路。将结果序列中的一个 换成这个回路此时的结果序列即为 而图也变成了下面的样子。重复进行步骤 2 。检查刚刚添加到结果序列中的节点节点 、、。我们发现节点 还存在未被遍历的边 和 因此我们从节点 出发重复步骤 1。假设我们的遍历路径为 此时我们找到了一个包含 的回路。将结果序列中的一个 换成这个回路此时的结果序列即为 而图也变成了下面的样子。重复进行步骤 2。检查刚刚添加到结果序列中的节点节点 、、。此时不存在未遍历的边因此结果序列 就是原图中的一个欧拉回路。算法结束。正确性证明我们通过反证法简要说明一下为什么步骤 1 中如果遇到一个节点 不存在未被删除的边即节点 的度数为 那么该节点必然是出发点 。首先假设 那么在遍历过程中为了最终进入节点 进入 的边数需要恰好比离开 的边数多 也就是说节点 的度数将减少一个奇数。然而由于原图存在欧拉回路因此节点 的初始度数为偶数。偶数减去奇数不可能等于 因此必然有 。至于为什么该算法可以遍历所有边简单来说是因为所有非零度节点是连通的。详细的证明需要用到一个关于连通性的反证法有兴趣的读者可以参考《Pearls in Graph Theory》一书中 3.1 节的相关证明[^5]。