2018年12月5日第13章：探索欧拉图与哈密顿图

最编程 2024-08-12 07:01:49

...

13.1 欧拉图与中国邮递员问题

1.设G是一个无向图，包含G的每条边的简单道路称为欧拉道路，包含G的每条边的简单回路称为欧拉回路，具有欧拉回路的图称为欧拉图。

2.连通图G是欧拉图，当且仅当G不含奇数度结点。

3.非平凡连通图G含有欧拉道路，当且仅当G最多有两个奇数度结点。

4.连通有向图G含有有向欧拉回路，当且仅当G中每个结点的入度等于出度。连通图G含有有向欧拉道路，当且仅当除最多两个结点外，其余每个结点的入度等于其出度，而这两个结点中的一个结点的入度比其出度多1，另一个结点的入度比其出度少1.

5.构造欧拉回路算法（Fleury算法）：

1).从G中任选一点 $v_0$ 和与 $v_0$ 关联的边 $e_0$ ，置 $s = v_0$ , $e = e_0$ .

2).记录s和e，并在G中标记e。设与e关联的另一结点 $u_0$ ,置 $s=u_0$ .

3).设从G中删去已标记过的全部k条边后得到的子图为 $G_k$ ,则

1.当 $G_k$ 为零图时，算法结束。

2.若在 $G_k$ 中与s关联的边都不是割边，则任选其中一边e',置e=e',转2).

3.若在 $G_k$ 中与s关联的边有割边e'且s是 $G_k$ 中的一度点，则令e'=e,转2);否则在 $G_k$ 中任选一条与s关联的非割边e''，令e=e''，转2).

6.求解无向图的中国邮递员问题算法：

1).若G不含奇度结点，则5介绍的方法构造欧拉回路，就是问题的解。

2).若G含有2k个奇度结点，则先求出其中任何两个结点之间的最短道路，然后再在这些道路之中找到k条道路 $P_1,P_2,…,P_k$ ，使得

①任何 $P_i$ 和 $P_j$ （i≠j）没有相同的起点和终点。

②在所有满足1)的k条道路的集合中， $P1,P2,…,P_k$ 的长度总和最短。

3).在所有满足1)的k条道路集合中， $P_1,P_2,…,P_k$ 在原图G中复制的所有出现在这k条道路上的边，设所得的图为G'.

4).造G‘的欧拉回路，即得到中国邮递员问题的解。