离散习题讲解（12）

她来听我的演唱会......

Q1:

判断给定的图是否有欧拉回路。如果有，构造一个欧拉回路。

A1:

a)

解释：

欧拉回路条件：一个图有欧拉回路，当且仅当所有顶点的度数都是偶数，并且图是连通的。
在这个图中，所有顶点的度数都是偶数，所以这个图满足有欧拉回路的条件。

构造欧拉回路：

我们可以通过试探法或者使用Fleury算法来构造欧拉回路。一个可能的欧拉回路是：

$ a, b, c, f, i, h, g, d, e, h, f, e, b, d, a $

因此，图中有欧拉回路。

b)

解释：

欧拉回路条件：一个图必须所有顶点的度数都是偶数才能有欧拉回路。在这个图中，顶点c的度数是奇数（度数为1），所以该图没有欧拉回路。
欧拉路径：如果图中恰好有两个顶点的度数是奇数，那么图中存在一个欧拉路径。

构造欧拉路径：

一个可能的欧拉路径是（从两个奇度顶点之一开始，到另一个奇度顶点结束）：

$ f, a, b, c, d, e, f, b, d, a, e, c $

因此，图中没有欧拉回路，但有欧拉路径。

c)

解释：

和b部分类似，这个图没有欧拉回路，因为顶点b的度数是奇数（度数为1）。对于欧拉回路，所有顶点的度数必须是偶数。
欧拉路径：由于图中恰好有两个奇度顶点，图中存在欧拉路径。

构造欧拉路径：

一个可能的欧拉路径是：

$ b, c, d, e, f, d, g, i, d, a, h, i, a, b, i, c $

因此，这个图没有欧拉回路，但有欧拉路径。

答案总结：

a) 该图有欧拉回路，一个可能的回路是：
$ a, b, c, f, i, h, g, d, e, h, f, e, b, d, a $
b) 该图没有欧拉回路，但有欧拉路径，一个可能的路径是：
$ f, a, b, c, d, e, f, b, d, a, e, c $
c) 该图没有欧拉回路，但有欧拉路径，一个可能的路径是：
$ b, c, d, e, f, d, g, i, d, a, h, i, a, b, i, c $

Q2:

Determine whether the given graph has a Hamilton circuit. If so, find such a circuit. If it does not, give an argument to show why no such circuit exists.

A2:

a)

解释：

哈密顿回路（Hamiltonian Circuit）的条件是图中必须存在一个经过每个顶点恰好一次并且回到起点的回路。
在这个图中，{c, f} 是一个割边（cut edge）。割边的定义是，如果删除该边，图就会被分成两个连通组件。
如果删除了 {c, f}，图就被分成了两个部分，且每个部分都无法包含完整的哈密顿回路。哈密顿回路要求图是连通的，且能够遍历所有的顶点。由于割边的存在，这两个部分中的任何一个都无法形成包含所有顶点的回路，因此没有哈密顿回路。

结论：由于割边 {c, f}，该图没有哈密顿回路。