欧拉路径和欧拉回路
欧拉路径即每条边只走一次且能遍历所有边的路径(一笔画)
欧拉回路即起点和终点为同一点的欧拉路径
对于无向图,所有边都是连通的。
存在欧拉路径的充分必要条件:度数为奇数的点只能有0或2个。
存在欧拉回路的充分必要条件:度数为奇数的点只能有0个。
对于有向图,所有边都是连通的。
存在欧拉路径的充分必要条件:要么所有点的入度都等于出度;要么除了两个点之外,其余所有点的出度等于入度,剩余的两个点,一个满足出度比入度多1(起点),另一个满足入度比出度多1(终点)。
存在欧拉回路的充分必要条件:所有点的出度均等于入度。