CS70Disc 02B

1. 简短答案

(a) 欧拉公式与面数

问题：一个连通的平面简单图的边数比顶点数多5。它有多少个面？

解答：面数 $ f = 7 $。

推导：使用欧拉公式 $ v - e + f = 2 $，其中 $ v $ 是顶点数，$ e $ 是边数，$ f $ 是面数。

设顶点数为 $ v $，则边数 $ e = v + 5 $。
将其代入欧拉公式： $ v - (v + 5) + f = 2 $ 简化得到： $ f - 5 = 2 f = 7 $

(b) 超立方体变为树的边数

问题：需要从一个三维超立方体中移除多少条边才能得到一棵树？

解答：需要移除 5 条边。

推导：

三维超立方体有 $ 2^3 = 8 $ 个顶点和 $ = 12 $ 条边。
对于 8 个顶点的树，边数为 $ 8 - 1 = 7 $。
因此，移除的边数为 $ 12 - 7 = 5 $。

(c) 多连通平面图的欧拉公式

问题：欧拉公式 $ v - e + f = 2 $ 需要平面图是连通的。那么对于有 $ k $ 个连通分量的平面图，类似的公式是什么？

解答：对于 $ k $ 个连通分量，类似的公式为： $ V - E + F = k + 1 $ 推导：

设第 $ i $ 个连通分量的顶点数、边数和面数分别为 $ v_i $、$ e_i $ 和 $ f_i $。
欧拉公式对每个分量都成立：$ v_i - e_i + f_i = 2 $。
将其对所有 $ k $ 个分量相加： $ _{i=1}^k (v_i - e_i + f_i) = 2k $
总顶点数 $ V = {i=1}^k v_i $，总边数 $ E = {i=1}^k e_i $，总面数 $ F = _{i=1}^k f_i $。
所以： $ V - E + F + (k - 1) = 2k $ 从而得到： $ V - E + F = k + 1 $

2. 总是、偶尔或从不

(a) G 可以用 4 种颜色进行顶点着色。

结论：可能是平面图，也可能是非平面图。

证明：

根据四色定理，任何平面图都可以用 4 种颜色着色。
非平面图的例子：$ K_{3,3} $，可以用 2 种颜色着色。

(b) G 需要 7 种颜色进行顶点着色。

结论：总是非平面图。

证明：

根据四色定理，如果一个图是平面图，则最多可用 4 种颜色着色。
反之，如果一个图需要超过 4 种颜色，则它必定是非平面图。

(c) $ e 3v - 6 $，其中 $ e $ 是 G 的边数，$ v $ 是 G 的顶点数。

结论：可能是平面图，也可能是非平面图。

证明：

每个平面图都满足此公式。
非平面图的例子：$ K_{3,3} $ 具有 9 条边和 6 个顶点，满足 $ 9 $。

(d) G 是连通的，且 G 中每个顶点的度数最多为 2。

结论：总是平面图。

证明：

如果 G 是树，则 G 必然是平面图。
如果 G 不是树，含有循环。每个顶点的度数最多为 2，因此 G 必须是单个大循环，可以在平面上画出。

(e) G 中每个顶点的度数最多为 2。

结论：总是平面图。

证明：

每个连通分量都是连接的，且没有顶点度数超过 2，因此每个分量都是平面图。

3. 图着色

证明最大度数为 $ k $ 的图是 $ k + 1 $ 可着色的

证明：

使用顶点数 $ n $ 进行归纳。
基例：当 $ n = 1 $ 时，图的最大度数为 0，且可用 1 种颜色着色。
归纳步骤：假设 $ P(n) $ 为真，考虑一个 $ n + 1 $ 顶点的图 $ G $，去掉一个顶点 $ v $，剩下的子图 $ H $ 的最大度数不超过 $ k $。
根据归纳假设，$ H $ 是 $ k + 1 $ 可着色的。
添加 $ v $，可以选择一种与其相邻顶点不同的颜色（最多有 $ k $ 个相邻顶点），因此 $ G $ 是 $ k + 1 $ 可着色的。

4.超立方体

注意 5 超立方体 $ G = (V, E) $ 的顶点集由 $ V = {0, 1}^n $ 给出（回忆一下，$\{0, 1\}^n$ 表示所有 n 位二进制字符串的集合）。如果两个顶点 $ x $ 和 $ y $ 在恰好一个位的位置上不同，则它们之间有一条边。

(a) 绘制 1、2 和 3 维超立方体，并使用相应的二进制字符串标记顶点。

1维超立方体：即一条线段
- 顶点：$ 0, 1 $
2维超立方体：即一个正方形
- 顶点：$ 00, 01, 10, 11 $
3维超立方体：即一个立方体
- 顶点：$ 000, 001, 010, 011, 100, 101, 110, 111 $

(b) 证明 n 维超立方体的边可以使用 n 种颜色进行着色，使得没有一对共享公共顶点的边具有相同的颜色。

考虑每条改变第 $ i $ 位的边，$ 1 i n $。每个顶点只接触到其中一条边，因为在任何二进制字符串中，改变第 $ i $ 位的方式只有一种。因此，将每条边用颜色 $ i $ 着色，确保每个顶点与 $ n $ 条不同颜色的边相邻，因为有 $ n $ 个不同的位可以改变，而且不同位上的边不会有相同的颜色。

例如，在三维情况下，颜色可以如下示例所示（红色代表第一个位，蓝色代表第二个位，绿色代表第三个位）：

000 --(红)--> 100
 |            |
(蓝)         (蓝)
 |            |
001 --(红)--> 101

替代解法（使用归纳法）：

基本情况：当 $ n = 1 $ 时，只有一条线的超立方体可以用 1 种颜色着色。
接下来，假设 $ n $ 维超立方体可以用 $ n $ 种颜色着色。注意，$ n + 1 $ 维超立方体由两个 $ n $ 维超立方体组成；每个超立方体都可以根据归纳假设用 $ n $ 种颜色着色。
我们可以用不同的颜色连接这两个 $ n $ 维超立方体的边，这将是我们的第 $ n + 1 $ 种颜色。由于这些新边总是连接来自每个子立方体的不同顶点，因此没有这些新边共享同一个顶点，从而有效地为 $ n + 1 $ 维超立方体着色。

(c) 证明对于任何 $ n $，n 维超立方体是二分图。

考虑具有偶数个 0 位的顶点和具有奇数个 0 位的顶点。每个具有偶数个 0 位的顶点只与具有奇数个 0 位的顶点相邻，因为每条边代表一次位的变化（无论是通过翻转 1 位增加 0 位，还是通过翻转 0 位减少 0 位）。设 $ L $ 为具有偶数个 0 位的顶点集，设 $ R $ 为具有奇数个 0 位的顶点集，那么没有两个相邻的顶点会属于同一集合。

对于三维情况下的示例如下：

$ L $ 为蓝色顶点，$ R $ 为红色顶点。

替代解法（使用归纳法和着色法）：

证明图是可二分的同样等价于它是二分图。首先，基本情况是一个仅有两个顶点的超立方体，显然是可二分的。然后注意，如果一个二分图的颜色交换仍然是有效的，因为如果端点颜色不同，交换颜色后仍然是不同的。现在，递归地对两个子立方体进行相同的二分着色，然后在一个子立方体中交换颜色。子立方体内部的边在归纳假设下是可行的。跨越的边是有效的，因为对应的顶点由于交换而具有不同的颜色。