wzf2000 离散数学笔记（14）——欧拉图、哈密尔顿图与二部图
Contents
欧拉图、哈密尔顿图与二部图
欧拉图
欧拉迹
在无孤立结点的图 $G$ 中，如果存在一条路，它经过图中每条边一次且仅一次，称此路为欧拉迹。
欧拉回路
在无孤立结点的图 $G$ 中，若存在一条回路，它经过图中每条边一次且仅一次，称此回路为欧拉回路。
称此图为欧拉图，或 E 图（Euler）。
欧拉图判定
定理 1：一个非空连通图（可以是多重图）是欧拉图当且仅当它不含奇数度的点。
证明：前推后显然，后推前考虑反证法。
假设一个边数最少的图，使得其不存在欧拉回路。
取出连通图中最大的闭迹 $C$，则剩余边构成的子图中任意一个边数大于 $0$ 的分支 $G'$ 都满足不含奇数度的点的性质，故都具有一条欧拉回路 $C'$。
而因为 $G$ 的连通性，$\exists v \in V(C) \cap V(C')$。（若不然，两个子图之间必定可以扩充）
则通过 $v$ 作为起点终点即可将 $C$ 与 $C'$ 合并得到 $CC'$ 获得一条 $G$ 的新的闭迹，与假设矛盾。
推论：一个连通图 $G$ 有欧拉迹当且仅当 $G$ 最多有两个奇点。
证明：前推后显然，后推前考虑将两个奇点之间连一条边，即可获得一条欧拉回路，再去掉这条边即得欧拉迹。
注：欧拉路与欧拉回路问题，也称一笔画问题。
定理 2：一个有向图 $D$ 具有欧拉迹，当且仅当 $D$ 是连通的，且除了两个顶点外，其余顶点的入度均等于出度。这两个特殊的顶点中一个顶点的入度比出度大 $1$，另一个顶点的入度比出度小 $1$。
求欧拉回路算法
中国邮递员问题
一个邮递员送信，每次要走遍他负责投递范围内的街道，然后再回到邮局。问他应该按怎样的路线走，使所走的路程最短？
如果用点表示交叉路口，用点之间的连线表示对应的街道，每条线上对应一个实数，它是相应街道的长度。原问题变成一个图论问题。
中国邮递员问题：在赋以非负权的连通图 $G$ 上，求一条最小权环游。
环游：经过一个图 $G$ 的每条边至少一次的闭回路。
求解：
若 $G$ 中每个点的度为偶数，$G$ 为欧拉图，则 $G$ 中的欧拉回路是最优环游。
若 $G$ 不是欧拉图，则 $G$ 的任何环游，包括 $G$ 的最优环游，通过某些边将超过一次。
则问题变为：给出一个连通图 $G$。
- 求 $E_1 \subseteq E$ 满足条件：在 $G$ 中重复 $E_1$ 中每条边，使得到的图 $G^*$ 是欧拉图（称这样的 $E_1$ 为可行集）。并且使 $E_1$ 的权尽可能小（称这样的可行集 $E_1$ 为最优集）。
- 求 $G^*$ 的欧拉回路.。
定理：$L$ 是无向连通图 $G$ 最佳邮路（最优环游）的充要条件是：
- $G$ 的每条路最多重复一次。
- 在 $G$ 的任意一个回路上，重复边长度之和不超过该回路长度的一半。
特例：若 $G$ 恰好含两个奇点，则只需要重复此二奇点之间的最短路即可。
哈密顿图
哈密顿问题
用一个十二面体代表地球，用它的二十个顶点分别代表世界上的二十个城市。要求沿十二面体的棱，走过每个城市一次且仅仅一次，最后回到出发点。
哈密顿图
设 $G = \langle V,E \rangle$ 是个无向有限图。
哈密顿路：通过 $G$ 中每个结点恰好一次的路。
哈密顿回路（H 圈）：通过 $G$ 中每个结点恰好一次的路。
哈密顿图（H 图）：具有哈密顿回路（H 全）的图。
设 $G$ 是多重图，$G’$ 是去掉 $G$ 中的多重边和环后得到的图，显然若 $G’$ 是 H 图，则 $G$ 也是 H 图，因此，只需讨论简单图。
哈密尔顿图的判定
定理 1（充分条件）：$G$ 是至少有 $3$ 个点的完全图，则 $G$ 是 $H$ 图。
定理 2：$G$ 是简单图，且 $n \ge 3$，若对 $G$ 中任一对不相邻点 $u,v$，都有 $d(u) + d(v) \ge n$ . 则 $G$ 是哈密顿图。
引理 1：设 $u,v$ 是 $G$ 的一对不相邻点，$d(u)+d(v) \ge n$。若 $G + uv$ 是 H 图 $\Leftrightarrow G$ 是 H 图。
定理 3：$G$ 是 H 图 $\Leftrightarrow C(G)$ 是 H 图。
定理 4：若 $C(G)=K_n \Leftrightarrow G$ 是 H 图。
定理 5：$G$ 是简单图，且 $n \ge 3, \delta \ge \frac{n}{2}$，则 $G$ 是 H 图。
定理 6：$G$ 是简单图，且 $n \ge 2$，若对 $G$ 中任一对不相邻点 $u,v$，都有 $d(u) + d(v) \ge n - 1$，则 $G$ 有 H 路。
利用此定理可得定理 2 另一种证明：
定理 7（必要条件）：若图 $G = \langle V,E \rangle$ 有 H 圈，则对 $V$ 的任何非空子集 $S$，均有 $W(G - S) \le |S|$，其中 $W(G - S)$ 是从 $G$ 中删去 $S$ 中所有结点及与这些结点关联的边所得到的子图的连通分支数。
定理 8：若 $G$ 是 Hamilton 圈 $\Rightarrow G$ 是 $2-$ 连通。
旅行商问题
H 圈问题不涉及边的长度，但是在许多实际问题中，每条边都可以有它的权。
旅行商问题（TSP）：一个商人欲到 $n$ 个城市推销商品，每两个城市 $i$ 和 $j$ 之间的距离为 $d_{ij}$，如何选择一条道路使得商人每个城市走一遍后回到起点，且所走路径最短。
图论语言：给定一个赋正权的完全图，求具有总长最短的 H 圈。
这个问题是 NPC 问题，一种好的精确求解法是分支与界法。
二部图
二部图
令 $G = \langle V,E \rangle$ 是无向图，如果可以将 $V$ 划分成两个子集 $V_1,V_2$，使得任何边 $(v_i,v_j) \in E$，$v_i \in V_1,v_j \in V_2$，则称 $G$ 是二部图，也称二分图，称 $V_1,V_2$ 是 $G$ 的互补的顶点子集。
完全二部图
令 $G = \langle V,E \rangle$ 是以 $V_1,V_2$ 为互补的顶点子集的二部图，如果 $V_1$ 中的每个节点都与 $V_2$ 中每个结点相邻接，则称 $G$ 是完全二部图。如果 $|V_1| = m,|V_2| = n$，则 $G$ 记作 $K_{m,n}$。
二部图的判定
定理：$G = \langle V,E \rangle$ 是二部图，当且仅当它的所有回路的长度都是偶数。
No Comments