离散数学作业 20251116 第九章

证明 Dijkstra 算法的正确性

即证明：当算法选择一个顶点 $u$ 并将其加入集合 $S$ 时，此时 $d[u]$ 的值等于其真实的从 $s$ 到 $u$ 的最短路径长度，即 $d[u]=\delta(s,u)$.

运用数学归纳法，显然第一步时 $S=\empty$，算法选择 $u=s$ 加入了 $S$，此时 $d[s]=\delta(s,s)=0$，成立。

显然加入 $u$ 时 $d[u]$ 是由一条路径松弛而来，故必然有 $d[u]\ge \delta(s,u)$。

假设 $d[u]>\delta(s,u)$，则在图中存在另一条从 $s$ 到 $u$ 的边 $P:s\to v_1 \to … \to x \to y \to … \to u$ ，使得 $x\in S,y\notin S$，且 $P$ 的长度 $l_p=\delta(s,u)$. 则 $l_P=\delta(s,u)=l_{sx}+w_{xy}+l_{yu}$。由于 $x\in S$，所以 $l_{sx}=\delta(s,x)=d[x]$。

由于将 $x$ 加入 $S$ 的时候算法已经将 $x$ 的所有邻居（包括 $y$ ）进行了松弛操作，故 $d[y]\le d[x]+w_{xy}$.

故 $d[u]>\delta(s,u)=d[x]+w_{xy}+l_{yu}\ge d[y]+l_{y,u}$，即 $d[u]>d[y]$。

而此时算法选择了 $u$，且 $u\notin S,y\notin S$ ，意味着 $d[u]\le d[y]$，矛盾！

故 Dijkstra 算法是正确的。

8.40

证明： (1) 马图是哈密顿图。

(2) 2x2、3x3、4x4 和 5x5 的小棋盘不是哈密顿图。

由染色法，将棋盘染成黑白二色，要求相邻两个格子不同色，每次移动必定跨越黑白。故若马图是哈密顿图，则一定黑白色格子数相同，所以 $3\times3,5\times5$ 不是哈密顿图。

$2\times 2$ 棋盘没有边，显然不是哈密顿图。

$4\times4$ 棋盘删去中间四个点后，$\omega(G-S)=6>|S|$，不是哈密顿图。

8.41

证明： 在一个图中奇顶点个数为 2K 个，则该图是 K 笔画的。

选取其中的 $2K-2$ 个奇顶点，两两连接，则图变为只有两个奇点的图，故存在一条欧拉路径，从其中一个奇点出发，到另一个奇点结束。

一条一条地删去刚刚连接的边，则图的笔画数+1. 故图的笔画数为 $1+(K-1)=K$.

9.2

在一个连通平面图中，若它有 $n$ 个顶点，$e$ 条边，每个面至少由 $k$ ($k \ge 3$) 条边围成，证明： $e \le \dfrac{k(n-2)}{k-2}$。

证明：

令 $G$ 为连通平面图，$n, e, f$ 分别为顶点数、边数、面数。

由欧拉公式，$n - e + f = 2$，故 $f = e - n + 2$。

$G$ 中所有面的度数之和 $\sum deg® = 2e$。

根据题设，$\forall r, deg® \ge k$， ($k \ge 3$)。

故 $\sum deg® \ge kf$。

所以 $$2e \ge kf$$。

将 $f = e - n + 2$ 代入：

$$2e \ge k(e - n + 2)$$，$$2e \ge ke - kn + 2k$$，$$kn - 2k \ge ke - 2e$$，$$k(n - 2) \ge e(k - 2)$$

因为 $k \ge 3$， $k-2 > 0$。

所以 $$e \le \dfrac{k(n - 2)}{k - 2}$$，证毕。

9.3

证明彼得森图是非平面图。

证明：

设彼得森图 $P$ 是平面图。

$P$ ：$n = 10$, $e = 15,g(P) = 5$（无 $C_3, C_4$）。

若 $P$ 是平面图，则其嵌入的每个面 $r$ 必有 $deg® \ge g(P) = 5$。

令 $k=5$。

根据 9.2 的结论 $e \le \frac{k(n - 2)}{k - 2}$：

$$e \le \frac{5(10 - 2)}{5 - 2}<15$$.

这与 $P$ 实际的边数 $e = 15$ 矛盾，故彼得森图是非平面图，证毕。

9.5

证明：小于 30 条边的平面简单图中存在度数 $\le 4$ 的顶点。

令 $G$ 为平面简单图， $e < 30$。

假设 $\forall v \in V, deg(v) > 4$，即 $deg(v) \ge 5$。

由握手引理， $\sum deg(v) = 2e$。

根据假设， $\sum deg(v) \ge 5n$。

$\implies 2e \ge 5n \implies n \le \frac{2e}{5}$。

对于 $n \ge 3$ 的简单平面图， $e \le 3n - 6$。

将 $n \le \frac{2e}{5}$ 代入：

$$e \le 3\left(\frac{2e}{5}\right) - 6$$

解得：$$30 \le e$$。

这与题设 $e < 30$ 矛盾。

$\therefore$ 假设 $\forall v \in V, deg(v) \ge 5$ 为假。

故 $G$ 中存在 $v$ 使得 $deg(v) \le 4$。

证毕。