欧拉路径和欧拉回路

欧拉路径即每条边只走一次且能遍历所有边的路径(一笔画)

欧拉回路即起点和终点为同一点的欧拉路径

  1. 对于无向图,所有边都是连通的。

    存在欧拉路径的充分必要条件:度数为奇数的点只能有0或2个。

    存在欧拉回路的充分必要条件:度数为奇数的点只能有0个。

  2. 对于有向图,所有边都是连通的。

    存在欧拉路径的充分必要条件:要么所有点的入度都等于出度;要么除了两个点之外,其余所有点的出度等于入度,剩余的两个点,一个满足出度比入度多1(起点),另一个满足入度比出度多1(终点)。

    存在欧拉回路的充分必要条件:所有点的出度均等于入度。