一、前置知识
1、连通、极大联通子图
- 连通：图中任意两点皆可互达
- 极大连通子图：
- 对连通图来说：是这个连通图本身
- 对非连通图来说： 有多个极大联通子图
2、回路、简单回路、简单路径
- 回路：从一个点到经过一些其他节点，再回到该点的一个路径。此时，除了起点和终点，其他节点也是可以重复出现的。
eg：A -> B -> C -> B -> A，这就是一个合法的回路。 - 简单回路：在路径中，只有起点和终点是可以重复出现的。
eg：A-> B -> C - > A - 简单路径：任何点都不能在路径中重复出现。
eg：A -> B -> C
3、欧拉回路、欧拉路径、欧拉图、半欧拉图
- 欧拉路径：经过每条边一次并且仅一次，经过所有边的路径
- 欧拉回路：欧拉路径的基础上，从起点开始，最后需要回到起点
- 欧拉图：存在欧拉回路的图
- 半欧拉图：存在欧拉路径的图
4、哈密尔顿路、哈密尔顿回路、哈密尔顿图
- 哈密尔顿路：在图论中，遍历图中每个顶点一次且仅一次的路线称为哈密尔顿路径。
- 哈密尔顿回路：遍历图中每个顶点一次且仅一次的回路(从哪里出发再回到哪里)称为哈密尔顿回路。
- 哈密尔顿图：具有哈密尔顿回路的图叫做哈密尔顿图
二、性质
1、有孤立点的图：
孤立点不会影响欧拉回路，直接忽略掉就好。
2、欧拉回路、欧拉路径、有向图、无向图
3、 扩展
- 设C是欧拉图G中的一个简单回路，将C中的边从图G中删去得到一个新的图G',则G'的每一个极大连通子图都有一条欧拉回路。
- 设C1,C2是图G的两个没有公共点，但至少有一个公共顶点的简单回路，我们可以将它们合并成一个新的简单的回路C'。
三、代码部分
四、相关例题
1、Colored Sticks
题意：给出一些木棍，木棍的两端有颜色，颜色相同的两根木棍可以接在一起，问能否将所有木棍接成一条直线。
考点：欧拉回路+并查集+字典树
思路：字典树将颜色对应数值存储起来。把木棍两端的颜色接在一起，用并查集判断图的连通性。判断是否是欧拉回路或者欧拉路径
