离散数学笔记(14)——欧拉图、哈密尔顿图与二部图

离散数学笔记(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$。

求欧拉回路算法

120

中国邮递员问题

一个邮递员送信,每次要走遍他负责投递范围内的街道,然后再回到邮局。问他应该按怎样的路线走,使所走的路程最短?

如果用点表示交叉路口,用点之间的连线表示对应的街道,每条线上对应一个实数,它是相应街道的长度。原问题变成一个图论问题。

中国邮递员问题:在赋以非负权的连通图 $G$ 上,求一条最小权环游。

环游:经过一个图 $G$ 的每条边至少一次的闭回路。

求解

若 $G$ 中每个点的度为偶数,$G$ 为欧拉图,则 $G$ 中的欧拉回路是最优环游。

若 $G$ 不是欧拉图,则 $G$ 的任何环游,包括 $G$ 的最优环游,通过某些边将超过一次。

则问题变为:给出一个连通图 $G$。

  1. 求 $E_1 \subseteq E$ 满足条件:在 $G$ 中重复 $E_1$ 中每条边,使得到的图 $G^*$ 是欧拉图(称这样的 $E_1$ 为可行集)。并且使 $E_1$ 的权尽可能小(称这样的可行集 $E_1$ 为最优集)。
  2. 求 $G^*$ 的欧拉回路.。

定理:$L$ 是无向连通图 $G$ 最佳邮路(最优环游)的充要条件是:

  1. $G$ 的每条路最多重复一次。
  2. 在 $G$ 的任意一个回路上,重复边长度之和不超过该回路长度的一半。

特例:若 $G$ 恰好含两个奇点,则只需要重复此二奇点之间的最短路即可。

哈密顿图

哈密顿问题

用一个十二面体代表地球,用它的二十个顶点分别代表世界上的二十个城市。要求沿十二面体的棱,走过每个城市一次且仅仅一次,最后回到出发点。

121

哈密顿图

设 $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$ 是哈密顿图。

122

引理 1:设 $u,v$ 是 $G$ 的一对不相邻点,$d(u)+d(v) \ge n$。若 $G + uv$ 是 H 图 $\Leftrightarrow G$ 是 H 图。

123

定理 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 路。

124

利用此定理可得定理 2 另一种证明:

125

定理 7(必要条件):若图 $G = \langle V,E \rangle$ 有 H 圈,则对 $V$ 的任何非空子集 $S$,均有 $W(G – S) \le |S|$,其中 $W(G – S)$ 是从 $G$ 中删去 $S$ 中所有结点及与这些结点关联的边所得到的子图的连通分支数。

126

定理 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$ 是二部图,当且仅当它的所有回路的长度都是偶数。

127

128

 

点赞 2

No Comments

Add your comment