有向图是否有欧拉路径及欧拉回路的依据

Question

老师您好，我想问一下，判断一个有向图是否有欧拉回路及欧拉路径，除了满足顶点入度和出度相关条件。有向图必须是强连通的吗？是不是只要是连通的就可以了呢。比如：1->2->3->4->5，这样的一个图，【1，2，3，4，5】就是一条欧拉路径呢,但是有向图所有顶点并不在同一个强连通分量中

Answer 1

liuyubobobo 2021-04-05 18:06:15

对于欧拉回路，肯定是强连通的(不考虑孤立点)。因为欧拉回路从一点出发，经过所有边，又回到这一点。经过所有边的过程，肯定也经过了所有点。所以整个回路中，肯定所有的点都是可以互相抵达的。

对于欧拉路径，是的，不一定强连通。你给的例子非常好。

继续加油！：）

• 提问者 weixin_慕慕4340848 #1

  非常感谢！