基本信息

---

下载

文档摘要

---

如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做

欧拉回路。

我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个

定理。

定理：存在欧拉路的条件：图是连通的，有且只有个奇点。

定理：存在欧拉回路的条件：图是连通的，有个奇点。

两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点

外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去

次数一定都是相等的，显然没有奇点。

求欧拉路的算法很简