图论导引 - 第三章 第二节：欧拉图 - 11/10

欧拉图 Eulerian Graphs

定义

如果存在一条包含图 $G$ 中每一条边的封闭的迹 trail，则连通图 $G$ 是欧拉图。这样的迹是一条欧拉迹（Eulerian Trail）。

• 注意，这个定义要求每条边恰好被遍历一次。回顾：迹要求所有边都不同。
• 且迹是封闭的！即从一个顶点出发，沿着边行走，最终回到起始顶点，且每条边恰好经过一次。

如果一个图不是欧拉图，但存在一条迹包含图 $G$ 的每一条边，该图 $G$ 是半欧拉图（semi-Eulerian）。

• 半欧拉图的迹不一定是封闭的！即不要求回到起始顶点。

注：半欧拉图中的迹也可以叫欧拉路径，即每条边恰好被遍历一次的路径；而欧拉迹也可以叫欧拉回路。

应用

欧拉图定义有助于区分不同类型的图在边遍历特性上的差异，在研究图的性质和解决相关问题（如路径规划、网络遍历等）中有重要作用。例如在物流配送路线规划中：

• 如果配送区域的道路图是欧拉图，就可以找到一条遍历所有道路且不重复的最优路线；
• 如果是半欧拉图，也能找到经过所有道路但可能需要额外考虑起始和结束点不同的较优路线；
• 而对于非欧拉图，则需要更复杂的策略来处理路径规划问题。

欧拉图的判定

如何找到欧拉图？如何证明一个图是欧拉图？一个图是欧拉图的充分必要条件是什么？

引理6.1：如果图 $G$ 中每个顶点的度数至少为 2，那么图 $G$ 包含一个圈。

证明：

• **选择起始顶点：**假设 $G$ 是一个简单图，设 $v_0$ 是 $G$ 的任意一个顶点，选择该顶点 $v_0$ 为起始顶点。
• 构建路径：从 $v_0$ 开始，沿着边移动到一个相邻顶点 $v_1$。由于每个顶点的度数至少为2，$v_1$ 至少有一个除了 $v_0$ 之外的邻居。继续添加邻居，归纳构建一条路径 $v_0\to v_1\to v_2\to \cdots$，使得对于所有的 $i$，$v_i$ 都与 $v_{i+1}$ 相邻。
• 检查重复顶点：由于图是有限的，这个过程最终肯定会出现重复顶点。假设 $v_k=v_j$ ($k>j$）。这意味着有一个循环 $v_j\to v_{j+1}\to \dots \to v_k$。
• 形成圈：循环 $v_j,v_{j+1},\dots ,v_k$ 形成了一个圈。如果 $j=0$，那么圈就是 $v_0\to v_1\to \dots \to v_k$。如果 $j>0$，那么圈是 $v_j\to v_{j+1}\to \dots \to v_k$。
• 这个证明依赖于图的有限性和每个顶点至少有两个邻居的事实，这保证了我们可以无限期地构建路径，直到我们遇到一个重复的顶点，从而形成一个圈。

定理6.2（欧拉，1736）：一个连通图 $G$ 是欧拉图当且仅当 $G$ 的每个顶点的度数都是偶数。

• 注意该定理的前提是图 $G$ 是连通图

证明：

• 证充分性：一个连通图是欧拉图 ⇒ 该连通图的每个顶点度数都是偶数
  • 假设 $P$ 是图 $G$ 的一条欧拉迹。
  • 每当 $P$ 经过一个顶点时，这个顶点的度数就会增加 $2$。
  • 由于每条边在 $P$ 中恰好出现一次，所以每个顶点的度数一定是偶数。
• 证必要性：一个连通图的每个顶点度数都是偶数 ⇒ 该连通图是欧拉图（运用对边数的数学归纳法）
  • 归纳假设：假设对于任何边数少于 $G$ 的图，若每个顶点的度数都是偶数，则该图是欧拉图。
  • 存在圈 $C$：由于 $G$ 是连通的，每个顶点的度数至少为 $2$，所以根据引理6.1，$G$ 包含一个圈 $C$ 。
  • **圈 $C$ 包含所有边：**如果 $C$ 包含了 $G$ 的每一条边，那么 $G$ 就是一个欧拉图，证明完成。
  • 圈 $C$ 不包含所有边：从 $G$ 中移除 $C$ 的边以形成一个新的可能不连通的图 $H$。
    • $H$ 的边数比 $G$ 少，并且其中每个顶点的度数仍然是偶数。
  • 应用归纳假设：由于图 $H$ 的边数比 $G$ 少，根据归纳假设，$H$ 的每个连通分量都有一条欧拉迹。
  • 连通性：由于 $H$ 的每个连通分量都与 $C$ 至少有一个共同顶点，可以从 $C$ 开始构建 $G$ 的欧拉迹。
    • 通过沿着圈 $C$ 的边前进直到到达 $H$ 的一个非孤立顶点，假设该顶点为起始顶点 $v_0$，追踪包含该顶点的 $H$ 的连通分量的欧拉迹，这样就可以再次回到该顶点 $v_0$，即再次回到 $C$。
    • 然后继续沿着 $C$ 的边前进直到到达 $H$ 的另一个连通分量的一个顶点 $v_1$，依此类推。
  • **构建欧拉迹：**上述过程会一直进行，直到最后回到初始起点 $v_0$，这样就可以得到图 $G$​​ 的一条欧拉迹。
  • 当回到初始起点时，就证明了图 $G$​ 是一个欧拉图。

推论6.3：一个连通图是欧拉图当且仅当它的边集可以被分割成互不相交的圈。

证明：

• 充分性（边集可分割成互不相交的圈⇒图是欧拉图）：
  • 假设连通图 $G$ 的边集可以被分割成互不相交的圈 $C_1,C_2,\cdots ,C_k$。
  • 对于每个圈 $C_i$，我们可以从任意一个顶点开始沿着圈走一圈，由于圈的性质，每条边恰好经过一次，且回到起始顶点，这样就得到了一条欧拉迹。
  • 因为这些圈是互不相交的，所以将这些圈的欧拉迹依次连接起来（因为图是连通的，这些圈之间有公共顶点可以连接），就可以得到一条包含图 $G$ 所有边的欧拉迹，所以 $G$ 是欧拉图。
• 必要性（图是欧拉图⇒边集可分割成互不相