欧拉路径问题——无向图的欧拉路径

如果给定一张无向图一条路径只需要恰好经过每条边一次而不需要回到起点那么这条路径被称为“欧拉路径”。与欧拉回路类似我们只要抓住进入每个点和离开每个点的边数关系就能得到无向图中存在欧拉路径的判定条件。判定条件如下一张无向图中存在欧拉回路当且仅当所有非零度节点是连通的且只有0或2个节点的度数为奇数其它节点的度数均为偶数。我们简要分析一下若欧拉路径的起点s和终点t相同那么它就是欧拉回路。此时图中有0个节点的度数为奇数。若欧拉路径的起点 和终点 不同那么为了最终离开 进入 的边数要恰好比离开 的边数少 因此 的度数是奇数。同理为了最终进入 进入 的边数要恰好比离开 的边数多 因此 的度数也是奇数。此时图中有 个节点的度数为奇数。我们仍然可以使用 Hierholzer 算法寻找无向图中的欧拉路径相关证明也是类似的这里不再赘述。只不过当图中有两个度数为奇数的点时必须从其中一个点开始执行深度优先搜索才能找到欧拉路径。因为欧拉路径的起点必然是这两者之一。