离散数学作业 20251107 第八章-2

8.27

(1) 完全图 $K_n$ 是欧拉图吗？是哈密顿图吗？

$n$ 是奇数时由于每个点的度数均为偶数，故为欧拉图；$n$ 是偶数时则不是。

$\delta(G)\ge n/2$，故是哈密顿图。

(2) 完全二分图是欧拉图吗？是哈密顿图吗？

当且仅当 $m,n$ 均为偶数时 $K_{m,n}$ 是欧拉图，其余不是。

当 $m \ne n$ 时，不妨 $m > n$，则 $\delta(G)=n<\dfrac{n+m}{2}$，不是哈密顿图。

当 $m=n$ 时，$\delta(G)=n=\dfrac{2n}{n}$，是哈密顿图。

8.28

(1) 给出一个图既是欧拉图又是哈密顿图的例子。

$K_n$ ， $n$ 为偶数。

(2) 给出一个图是欧拉图，但不是哈密顿图的例子。

(3) 给出一个图是哈密顿图，但不是欧拉图的例子。

（中间的交叉点不是图的顶点）

8.33

若图 $G$ 中任意两点均存在一条哈密顿通路相连，则称 $G$ 是哈密顿连通的。试证明： 若 $G$ 是哈密顿连通的，且 $n \ge 4$，则边数 $e$ 满足 $e \ge \left[(3n+1)/2\right]$。

证明：

假设 $\delta(G)=1$，设 $deg(u)=1$，则取 $w_1,w_2$ 满足 $w_1,w_2 \ne u$ ，存在从 $w_1$ 到 $w_2$ 的哈密顿通路，而这个通路显然不能经过 $u$，矛盾。

假设 $\delta(G)=2$，假设 $\delta(G) = 2$。 令 $v$ 是一个 2 度顶点，其邻居为 $N(v) = {u, w}$。因为 $n \ge 4$，所以存在 $z \in V(G) \setminus {u, v, w}$，从 $u$ 到 $w$ 的哈密顿通路经过 $v,z$，而这也是不可能的，矛盾。

故 $\delta(G)\ge 3$，由握手定理，$2e \ge 3n$，$e \ge \left[(3n+1)/2\right]$，证毕！

8.37

若一个图中每一条边能给定一个方向，使得得到的有向图是强连通的，则这个图称为可定向的。

(1) 证明任意一个欧拉图是可定向的。

证明：

沿着欧拉回路走一圈，将边定向置为同向。

对于任意 $u,v\in G$，存在一条回路满足 $u\to v \to u$，故 $u,v$ 强连通。则图 $G$ 强连通。

(2) 证明任意一个哈密顿图是可定向的。

沿着哈密顿回路走一圈，将边定向置为同向。剩下未走过的边任意定向。

对于任意 $u,v\in G$，存在一条回路满足 $u\to v \to u$，故 $u,v$ 强连通。则图 $G$ 强连通。

(3) 证明一个连通图是可定向的当且仅当图的每条边至少在一条回路上。

若连通图 $G$ 是可定向的。

假设存在一条边 $e\in E(G)$，满足其不在任何一条回路上，假设这个边连接的两点为 $u,v$，定向为 $u\to v$。

因为 $e$ 不在回路上，所以不存在 $v\to u$ 的路径。故 $u,v$ 非强连通，矛盾！必要性成立。

若图的每条边至少在一条回路上。

则对于任意一条回路，由于回路上任意两点强连通，则可以回路上的边全部定同向，并将其缩成一个点，则最后的缩点结果为 $f(G)=v$，$v$ 是一个点。则图是强连通的，并且可以定向。