欧拉路径&哈密尔顿路径

1. 啥是这俩东西？

   1. 欧拉路径 指 把图上所有边都走一遍的路径。
   • 如果一个回路是欧拉路径，则称为欧拉回路。
   2. 哈密尔顿路径 指 把图上所有点都走一遍的路径。
   • 如果一个回路是哈密尔顿路径，则称为哈密尔顿回路。

2. 已知一个无向图，怎么样这两种路径才会存在？

• 如果有最多两个度数是奇数的点，那么这个图存在欧拉路径，起点是一个度数是奇数的点，终点也是。
• 如果这个图没有度数是奇数的点，那么这个图存在欧拉回路（也就是环），那么它的起点就是终点。
• 如果有$n$点，并且每个点的度数都$\ge \begin{cases}\frac n2&n\bmod 2=0\\\frac{n+1}2&n\bmod2=1\end{cases}$，那么存在哈密尔顿回路。

3. 求的方法

DFS。