图论——欧拉回路

一、前置知识

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'的每一个极大连通子图都有一条欧拉回路。
• 设C₁,C₂是图G的两个没有公共点，但至少有一个公共顶点的简单回路，我们可以将它们合并成一个新的简单的回路C'。

三、代码部分

四、相关例题

1、Colored Sticks

题意：给出一些木棍，木棍的两端有颜色，颜色相同的两根木棍可以接在一起，问能否将所有木棍接成一条直线。

考点：欧拉回路+并查集+字典树

思路：字典树将颜色对应数值存储起来。把木棍两端的颜色接在一起，用并查集判断图的连通性。判断是否是欧拉回路或者欧拉路径