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

来源：13-5 有向图求解欧拉回路

weixin_慕慕4340848

2021-04-05

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

写回答

1回答

liuyubobobo

2021-04-05

已采纳

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

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

继续加油！：）

weixin_慕慕4340848

非常感谢！

2021-04-07

共1条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1599 学习 · 330 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1