欧拉图的相关概念

simple_child · 2025-08-19 18:00:05 · 个人记录

事情是这样的，因为欧拉图导致我今天做 CSP 2024 提高级第一轮时选择题错了一题，所以先来小写一点概念。

小学奥数之一笔画问题。

• 欧拉路径：经过连通图中所有边恰好一次的迹称为 欧拉路径。 ::::info[什么是迹]{open} 迹 (trail)：对于一条途径 w，若 e_1, e_2, \ldots, e_k 两两互不相同，则称 w 是一条迹。 ::::info[什么是途径] 途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 w 是一个边的序列 e_1, e_2, \ldots, e_k，使得存在一个顶点序列 v_0, v_1, \ldots, v_k 满足 e_i = (v_{i-1}, v_i)，其中 i \in [1, k]。这样的途径可以简写为 v_0 \to v_1 \to v_2 \to \cdots \to v_k。通常来说，边的数量 k 被称作这条途径的 长度（如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义）。
• 欧拉回路：经过连通图中所有边恰好一次的回路称为 欧拉回路。 ::::info[什么是回路]{open} 回路 (circuit)：对于一条迹 w，若 v_0 = v_k，则称 w 是一条回路。 ::::
• 欧拉图：有欧拉回路的图称为 欧拉图。
• 半欧拉图：有欧拉路径但没有欧拉回路的图称为 半欧拉图。 ::::warning[Warning]{open} 此处定义中虽然使用「路径」一词，但严格说来此处使用的概念应该是「迹（trail）」。欧拉路径与欧拉回路仅能使用每条边恰好一次，但并没有对经过顶点的情况进行限制。 :::: 欧拉图能够以任意一点作为起点一笔画整张图然后回到该点，而半欧拉图只能从 S 开始，T\neq S 结束一笔画。