1.1 欧拉图问题

该节只考虑无向图

引例：

哥尼斯堡七桥问题

问题描述

要求作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。

问题解决

哥尼斯堡七桥问题是无解的。我们考虑路径中的任意一个点 $V$，所有连接 $V$ 的桥可以分为用于进入 $V$ 的桥与离开 $V$ 的桥，因为不能在 $V$ 点停留，所以进入 $V$ 的桥与离开 $V$ 的桥数量相同，故与 $V$ 连接的桥的数量必然是偶数，这是问题有解的必要条件。而观察可知，该图中存在桥数为奇数的点，故七桥问题无解。

问题延申

什么样的图形能够 “一笔画”？

图的定义

• 图 (Graph) 是一个有序二元组 $G=(V,E)$
• V：顶点集合，$V=\{A,B,C,D\}$，用 $|V|$ 或 $v(G)$ 或 $v$ 表示元素个数即顶点数
• E：边集，由 $V$ 中的顶点组成的无序对组成的集合（多重集），用 $|E|$ 或 $e(G)$ 或 $e$ 表示元素个数即边数

边集的表示：

$$\begin{array}{rl}& E=\{AB,AC,AD,BC,CD\}\\ or& E=\{AB,AC,AD,BC,CD\}\\ or& E=\{\{A,B\},\{A,C\},\{A,D\},\{B,C\},\{C,D\}\}\end{array}$$

NOTE

任何边都是顶点的二元子集 (多重集) $E$ 是 $V$ 的二元子集构成的集合，即：

$$E\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$$

超图 (hypergraph)：存在可以连接 $k⩾2$ 条边的超边 (hyperedge)

图中圈圈即可视为超边，当然你甚至可以把点视为超边

• 相邻：一条边的两端点相邻
• 关联：端点与边关联
• 环：端点重合的边 (如 $C_1$)
• 重边：端点相同的边 (如 $C_2$)

• 有限图：$V$ 与 $E$ 有限的图
• 平凡图：只有一个顶点的图
• 简单图：不含重边和环的图
• 度数 $d(v)$： 与 $v$ 关联的边数（计算度数时环算两条边）
• 最大度：$\Delta (G)=max\{d(v)|v\in V\}$
• 最小度：$\delta (G)=min\{d(v)|v\in V\}$

度和关系式

在任意图中，有：

$$\sum _{v\in V}d(v)=2|E|$$

证明

只有一条边时，度数和为 $2$，每增加一条边，度数和都增大 $2$，所以任意图的度数和为边数的两倍。

NOTE

由度和关系式可得：在任何图中，奇度点个数为偶数

证明：

由关系式知度数和为偶数，而偶度点度数和为偶数，故奇度点度数和只能是偶数，而偶数个奇数相加才是偶数，故奇度点的个数为偶数。

Euler 图

• 途径：点边交错出现的有向序列，满足相邻元素关联$v_1,e_1,v_2,e_2,v_3$
• 迹：边互不相同的途径
• 路：点互不相同的迹
• 圈：首尾相连的路
• 连通性：如果 $G$ 中任意两个顶点间都存在一条路，则 $G$ 连通，否则称 $G$ 不连通
• 连通分量 / 连通分支：极大连通子图
  比如，对于 图 1，设 $G$ 由 $C_3,C_4$ 构成，$C_3,C_4$ 内部连通而彼此不连通，则 $C_3,C_4$ 为 $G$ 的连通分量
• Euler 迹：经过图的每一条边的迹
• Euler 环游：起点与终点相同的 (闭的) Euler 迹
• Euler 通路：起点与终点不同的 (开的) Euler 迹
• Euler 图：存在 Euler 环游的图

定理 1：非平凡连通图 G 是 Euler 图的充要条件是 G 没有奇度点

为了证明这个定理，我们介绍两个引理：

引理 1

若简单图 $G$ 的 $d_{min}=k$，满足 $k⩾2$，则 $G$ 必然包含一个边数至少为 $k+1$ 的圈

证明

取图 $G$ 的一条长度最长的路 $P$，其经过的 $t+1$ 个点依次记为 $v_0,v_1,...,v_{t-1},v_t$，则点 $v_0$ 与点 $v_t$ 的相邻点都在路 $P$ 上（想想为什么？）由于 $G$ 的最小度 $d_{min}$ 至少为 $k$，故点 $v_0$ 至少有 $k$ 个邻点。设其为 $v_{i_1},v_{i_2},...,v_{i_k}(i_1⩽i_2⩽...⩽i_k)$，从而有 $k⩽i_k⩽t$，于是 $v_0,v_1,...,v_k$ 为图 $G$ 中的一个包含 $i_k+1⩾k+1$ 条边的圈，引理 1 得证（自己画画图会清晰很多）。

引理 2

设连通图 $G$ 中有一圈 $C$，$G^{{}^{\prime }}$ 是 $G$ 去掉 $C$ 中所有的边所得的图，若 $H$ 是 $G^{\prime }$ 的任意一个连通分量 (连通分支)，则:

$$V(C)\cap V(H)\ne \varnothing$$

证明:

1. 当 $G^{{}^{\prime }}$ 连通时，$H=G^{{}^{\prime }},V(H)=V(G^{{}^{\prime }})=V(G),V(C)\cap V(H)=V(C)\cap V(G)=V(C)$ 因为 $V(C)\ne \varnothing$，所以原命题成立。
2. 当 $G^{{}^{\prime }}$ 不连通时，假设：$V(C)\cap V(H_1)=\varnothing$，即 $C$ 上的点都不在 $H_1$ 上，则连接 $C$ 上的点使 $G$ 还原为 $G^{{}^{\prime }}$ 对 $H_1$ 与其他连通子图是否连通无影响，因为 $H_1$ 为 $G^{{}^{\prime }}$ 的连通分量，所以 $H_1$ 也为 $G$ 的连通分量，这与 $G$ 连通矛盾，所以假设不成立，原命题成立

综上，引理 2 得证。

利用两个引理，我们来证明定理 1：

定理 1：非平凡连通图 $G$ 是 Euler 图的充要条件是 $G$ 没有奇度点

必要性

证明过程同 “七桥”，当沿着 Euler 环游前进时，所经过的每一个点必定是 “一进一出，$n$ 进 $n$ 出”，故所有点都为偶度点。必要性证毕。

充分性

对于所有点都是偶度点的非平凡连通图 $G$，因为重边和环不影响 $G$ 是否为 Euler 图 (想想为什么?)，我们去掉所有环和重边 (把重边变成单边)，使 $G$ 等价于简单图，因为 $G$ 连通，不存在零度点，故 $\delta (G)=k⩾2$，根据引理 1，至少存在一个长度为 $k+1⩾3$ 的环 $C$，根据引理 2，去掉 $C$ 中所有的边得到图 $G^{{}^{\prime }}$，则 $G^{{}^{\prime }}$ 的所有连通分量都与 $C$ 有至少一个公共点，设非平凡连通分量分别为 $H_1,H_2,...,H_n$，与 $C$ 的公共点分别为 $V_1,V_2,...,V_n$，如果所有非平凡连通分量都为 Euler 图，那么我们从 $V_{i_1}$ 出发，经过 $H_{i_1}$ 的 Euler 环游回到 $V_{i_1}$，再沿 $C$ 到达 $V_{i_2}$，以此类推，可以得到一个 $G$ 的 Euler 环游，即证明了 $G$ 是 Euler 图，所以要证 $G$ 是 Euler 图，只要证 $H_1,H_2,...,H_n$ 都是 Euler 图。

对于 $H_i$，其与 $C$ 的公共点相对于 $G$ 来说度数减小 $2$，而其他点度数不变，而 $G$ 只有偶度点，故 $H_i$ 是没有奇度点的非平凡连通图，这样我们就缩小了问题规模，故要证无奇度点非平凡连通图 $G$ 是 Euler 图我们只要证所有顶点数小于 $G$ 的无奇度点非平凡连通图都为 Euler 图就可以了。

使用第二类数学归纳法：设 $G_v$ 为顶点数为 $v$ 的无奇度点非平凡连通图，当 $v=2$ 时，不难证明 $G_2$ 是 Euler 图，记 “$G_v$ 是 Euler 图” 为结论 v，由上面的推论可知，由结论 2 可得结论 3，由结论 2，结论 3 可得结论 4，由结论 2，结论 3，结论 4 可得结论 5…… 以此类推，最终我们得到：所有没有奇度点的非平凡连通图 $G$ 都是 Euler 图。充分性证毕。

综上，定理 1 证毕。

---