全局偏好、部分匹配、合并稳定配对、积累错误、图证明、二分图

(a) 配对结果为：对每个 \(i \in \{1, 2, \ldots, n\}\)，都有 \((C_i, J_i)\)。这一结果可以用归纳法证明：

基础情况：当 \(n = 1\) 时，唯一的配对是 \((C_1, J_1)\)，因此基础情况显然成立。

现在假设这对某个 \(n \in \mathbb{N}\) 成立。在 \(n + 1\) 个工作岗位和 \(n + 1\) 个候选人的情况下，第一天所有 \(n + 1\) 个工作岗位都会向 \(C_1\) 求婚。\(C_1\) 最偏好 \(J_1\)，其余工作岗位被拒绝。这剩下 \(n\) 个未配对的工作岗位和 \(n\) 个未配对的候选人，他们的偏好与之前相同（在 \((C_1, J_1)\) 配对之后）。由归纳假设，第 \(i\) 偏好的候选人将与第 \(i\) 偏好的工作岗位配对。

(b) 配对结果仍为：对每个 \(i \in \{1, 2, \ldots, n\}\)，都有 \((J_i, C_i)\)。这可以用与上述相同的归纳法证明，只需将"工作岗位"与"候选人"互换。

(c) 我们知道工作岗位求婚产生的是对候选人而言最差（candidate-pessimal）的稳定配对。我们也知道候选人求婚产生的是对候选人而言最优（candidate-optimal）的稳定配对。我们发现候选人最优配对与候选人最差配对是相同的。这意味着只有一个稳定配对，因为对候选人而言最好和最坏的配对是同一个配对。

(a) 我们按如下方式构造一个标准稳定匹配问题的实例。按照提示，为每个实体 \(e\) 引入一个虚构伴侣 \(r_e\)（不妨称之为机器人）。注意，我们为每个实体各引入一个机器人，即机器人的数量等于候选人与工作的总数。为简便起见，称每个机器人 \(r_e\) 由引入它的实体 \(e\) 所拥有。

每个机器人 \(r_e\) 最偏好其主人 \(e\)，即将其主人放在其偏好列表的首位。其偏好列表的其余部分可以是任意的，包含所有其他主人以及另一类实体的机器人。实体 \(e\) 将机器人 \(r_e\) 放在其偏好列表中恰好位于它愿意匹配的最后一个实体之后。也就是说，主人对机器人的喜欢程度高于它不愿意匹配的任何实体，但低于它愿意匹配的实体。其他机器人可以按任意顺序排在 \(e\) 的列表中。

对于这个我们称之为机器人实例 \(I\) 的稳定匹配问题实例，求婚-拒绝算法会给出一个稳定匹配 \(M\)。

为了提取所需的部分匹配，我们只需移除 \(M\) 中所有至少包含一个机器人的配对（两个机器人可能互相匹配）。我们将每个未被匹配的实体称为单身。我们观察到，实体 \(e\) 永远不会与另一个实体 \(e'\) 的机器人 \(r_{e'}\) 匹配，因为此时 \(e\) 和它的机器人 \(r_e\) 会构成一个 rogue couple（\(r_e\) 比其他主人更偏好 \(e\)，而 \(e\) 比其他机器人更偏好 \(r_e\)）。剩下的就是要证明这满足题目中规定的稳定性：

• 不存在某个已匹配的实体 \(e\) 宁愿保持单身而不愿与当前伴侣在一起，因为否则 \(e\) 和 \(r_e\) 会在 \(M\) 中构成一个 rogue couple；

• 不存在某个已匹配/已招满的工作 \(j\) 与某个单身的候选人 \(c\) 彼此都更偏好与对方匹配，因为否则 \(j\) 和 \(c\) 会在 \(M\) 中构成一个 rogue couple；

• 不存在某个已匹配的工作 \(j\) 与某个已匹配的候选人 \(c\) 彼此都更偏好与对方而非当前伴侣匹配，因为否则 \(j\) 和 \(c\) 会在 \(M\) 中构成一个 rogue couple；

• 同样地，不存在某个单身的工作 \(j\) 与某个已匹配的候选人 \(c\) 彼此都更偏好与对方匹配而非保持当前状态，因为否则 \(j\) 和 \(c\) 会在 \(M\) 中构成一个 rogue couple；

• 不存在某个单身的工作 \(j\) 与某个单身的候选人 \(c\) 彼此都更偏好与对方在一起而非保持单身，因为否则 \(j\) 和 \(c\) 会在 \(M\) 中构成一个 rogue couple。

因此，所得的部分匹配是稳定的。

(b) 我们使用反证法。假设存在某个工作 \(j_1\)，在稳定配对 \(S\) 中与候选人 \(c_1\) 配对，但在稳定配对 \(T\) 中单身。在稳定配对 \(S\) 中 \(j_1\) 和 \(c_1\) 配对意味着 \(j_1\) 和 \(c_1\) 都更偏好与对方在一起而非保持单身。由于 \(T\) 是稳定配对且 \(j_1\) 单身，\(c_1\) 在 \(T\) 中必然与某个工作 \(j_2\) 配对，且 \(c_1\) 对 \(j_2\) 的偏好高于 \(j_1\)。（如果 \(c_1\) 在 \(T\) 中单身，或者与一个 \(c_1\) 不比对 \(j_1\) 更偏好的工作配对，那么 \((j_1, c_1)\) 就会在 \(T\) 中构成一个 rogue couple，矛盾。）

由于 \(j_2\) 在 \(T\) 中与 \(c_1\) 配对，它在 \(S\) 中必然与某个候选人 \(c_2\) 配对，且 \(j_2\) 对 \(c_2\) 的偏好高于 \(c_1\)。这个过程继续下去（\(c_2\) 在 \(T\) 中必须与某个 \(j_3\) 配对，\(j_3\) 在 \(S\) 中必须与某个 \(c_3\) 配对，等等），其规律是 \((c_i, j_i)\) 在 \(S\) 中，而 \((j_i, c_{i-1})\) 在 \(T\) 中。由于工作在数量上是有限的，该过程必然在某个时刻 \(i\) 遇到 \(j_1\)。此时 \((j_1 = j_i, c_{i-1})\) 在 \(T\) 中，这意味着 \(j_1\) 在 \(T\) 中是匹配的。

对候选人也可以给出类似的论证。

这与 \(j_1\) 在 \(T\) 中单身的假设矛盾。由于没有任何工作或候选人可以在一个稳定配对中匹配而在另一个稳定配对中单身，每个工作或候选人要么在所有稳定配对中都匹配，要么在所有稳定配对中都单身。

(a) \(R \wedge R' = \{(A,3), (B,4), (C,1), (D,2)\}\)。通过考虑工作与候选人的不同组合可以看出该配对是稳定的。例如，\(A\) 对 \(2\) 的偏好高于其当前伴侣 \(3\)。然而，\(2\) 对当前伴侣 \(D\) 的偏好高于 \(A\)。类似地，\(A\) 最偏好 \(1\)，但 \(1\) 对当前伴侣 \(C\) 的偏好高于 \(A\)。我们可以通过类似地考察其余配对来证明该配对的稳定性。

(b) 设 \(j\) 是一个工作，它在 \(R\) 和 \(R'\) 中的伴侣分别为 \(c\) 和 \(c'\)，不妨设 \(c\) 在 \(j\) 的列表中排在 \(c'\) 之前（即 \(j\) 更偏好 \(c\)）。那么 \(j\) 在 \(R \wedge R'\) 中的伴侣就是 \(c\)，\(j\) 对 \(c\) 的偏好高于 \(c'\)。然而，若 \(j\) 对 \(R\) 或 \(R'\) 的偏好高于 \(R \wedge R'\)，则 \(j\) 必须对 \(c\) 或 \(c'\) 的偏好高于 \(c\)，这是不可能的（因为 \(c\) 在 \(j\) 的列表中排在 \(c'\) 之前）。

(c) 设 \(J\) 和 \(C\) 分别为偏好 \(R\) 甚于 \(R'\) 的工作和候选人的集合，\(J'\) 和 \(C'\) 分别为偏好 \(R'\) 甚于 \(R\) 的工作和候选人的集合。注意 \(|J| + |J'| = |C| + |C'|\)，因为左边是在两个配对中伴侣不同的工作的数量，右边是在两个配对中伴侣不同的候选人的数量。

现在，在 \(R\) 中不可能存在一对 \((j, c)\) 使得 \(j \in J\) 且 \(c \in C\)，因为这样 \((j, c)\) 在 \(R'\) 中就会构成一个 rogue couple。因此，\(J\) 中每个工作在 \(R\) 中的伴侣必须属于 \(C'\)，从而 \(|J| \le |C'|\)。类似地，\(J'\) 中每个工作在 \(R'\) 中的伴侣必须属于 \(C\)，从而 \(|J'| \le |C|\)。

由于 \(|J| + |J'| = |C| + |C'|\)，这两个不等式必须同时取等号，因此 \(|J'| = |C|\) 且 \(|J| = |C'|\)。结论就很显然了：如果工作 \(j\) 与候选人 \(c\) 在其中一个配对中是伴侣但在另一个中不是，那么

• 要么 \(j \in J\) 且 \(c \in C'\)，即 \(j\) 偏好 \(R\) 甚于 \(R'\) 且 \(c\) 偏好 \(R'\) 甚于 \(R\)，

• 要么 \(j \in J'\) 且 \(c \in C\)，即 \(j\) 偏好 \(R'\) 甚于 \(R\) 且 \(c\) 偏好 \(R\) 甚于 \(R'\)。

(d) (i) 如果 \(R \wedge R'\) 不是一个配对，那么原因必是两个工作得到了同一个候选人，或两个候选人得到了同一个工作。不妨设是前者，即 \((j, c) \in R\) 且 \((j', c) \in R'\) 导致了冲突。因此 \(j\) 偏好 \(R\) 甚于 \(R'\)，\(j'\) 偏好 \(R'\) 甚于 \(R\)。利用 (c) 部分的结论，这意味着 \(c\) 对 \(R'\) 的偏好高于 \(R\)，同时也对 \(R\) 的偏好高于 \(R'\)，矛盾。

(ii) 现在假设 \(R \wedge R'\) 中存在一个 rogue couple \((j, c)\)。那么 \(j\) 对 \(c\) 的严格偏好高于其在 \(R\) 和 \(R'\) 中的伴侣。此外，\(c\) 对 \(j\) 的偏好高于其在 \(R \wedge R'\) 中的伴侣。设 \(c\) 在 \(R\) 和 \(R'\) 中的伴侣分别为 \(j_1\) 和 \(j_2\)。如果 \(c\) 最终与 \(j_1\) 匹配，则 \((j, c)\) 是 \(R\) 中的 rogue couple；如果 \(c\) 最终与 \(j_2\) 匹配，则 \((j, c)\) 是 \(R'\) 中的 rogue couple。由于 \(c\) 的伴侣只有这两种可能，无论哪种情况都导出矛盾。

错误在于下述论证：「每个 \((n+1)\) 个顶点且最小度数为 \(1\) 的图都可以从一个 \(n\) 个顶点且最小度数为 \(1\) 的图再添加 \(1\) 个顶点得到」。证明并没有从任意一张 \((n+1)\) 个顶点的图出发，而只是考虑了那些可以从 \(n\) 顶点、最小度数为 \(1\) 的图构造出来的 \((n+1)\) 顶点图。

作为一个反例，考虑一张 \(4\) 个顶点的图，顶点集为 \(V = \{1, 2, 3, 4\}\)，边集为 \(E = \{\{1, 2\}, \{3, 4\}\}\)。该图中每个顶点的度数都是 \(1\)，但不可能从任何一张 \(3\) 个顶点且最小度数为 \(1\) 的图构造出这张 \(4\) 顶点的图。

更一般地，这是数学归纳法中 build-up error（累加误差） 的一个例子。它通常源于一个错误假设：每个具有某种性质的 \(n+1\) 规模图都可以从具有同样性质的 \(n\) 规模图「累加」得到。（这一假设对某些性质成立，但对另一些性质——比如上述论证中的性质——并不成立。）

避免意外 build-up error 的一种方法是：在归纳步骤中使用「shrink down, grow back（先缩小、再长大）**」的过程——从一张 \(n+1\) 规模的图开始，移除一个顶点（或一条边），把归纳假设 \(P(n)\) 应用到较小的图上，然后再把该顶点（或边）加回来，并论证 \(P(n+1)\) 成立。

我们来看看若用这种方法尝试证明上述命题会发生什么。在归纳步骤中，我们必须证明：对所有 \(n \ge 1\)，\(P(n)\) 蕴含 \(P(n+1)\)。考虑一张 \((n+1)\) 个顶点的图 \(G\)，其中每个顶点的度数至少为 \(1\)。移除任意一个顶点 \(v\)，留下一张 \(n\) 个顶点的图 \(G'\)，其中每个顶点的度数……呃——糟糕！简化后的图 \(G'\) 中可能出现度数为 \(0\) 的顶点，使得归纳假设 \(P(n)\) 无法适用！我们卡住了——这恰恰说明原命题是错误的。

(a) 我们对城市数 \(n\) 进行归纳。

Base case（基础情形）： 当 \(n = 2\) 时，两个城市之间总有一条道路从一个城市通向另一个城市。

Inductive hypothesis（归纳假设）： 设有 \(k\) 个城市时，存在一个城市 \(c\)，从其他任意城市出发最多经过 \(2\) 条道路就能到达 \(c\)。

Inductive step（归纳步骤）： 考虑 \(k+1\) 个城市的情形。移除其中一个城市 \(d\) 以及所有与 \(d\) 相连的道路。现在剩下 \(k\) 个城市，由归纳假设，存在某个城市 \(c\)，从其他任意城市出发最多经过 \(2\) 条道路就能到达 \(c\)。令 \(A\) 为有一条道路通向 \(c\) 的城市集合，\(B\) 为从 \(c\) 出发经过 \(2\) 条道路才能到达的城市集合。归纳假设表明，这 \(k\) 个城市构成的集合 \(S\) 满足 \(S = \{c\} \cup A \cup B\)。

现在把 \(d\) 以及所有与 \(d\) 相连的道路加回来。

在 \(d\) 与 \(S\) 中每个城市之间，必定有一条道路从一个城市通向另一个城市。

• 若至少存在一条道路从 \(d\) 通向 \(\{c\} \cup A\) 中的某个城市，则 \(c\) 仍然可以从 \(d\) 出发最多经过 \(2\) 条道路到达。

• 否则，若所有来自 \(\{c\} \cup A\) 的道路都指向 \(d\)，则 \(d\) 可以从 \(B\) 中的任意城市出发最多经过 \(2\) 条道路到达，因为 \(B\) 中的每个城市都可以先走一条道路到达 \(A\) 中的某个城市，再走一条道路到达 \(d\)。

无论哪种情形，新的 \(k+1\) 个城市中都存在一个城市，从其他任意城市出发最多经过 \(2\) 条道路就能到达。

(b) 把 \(2m\) 个奇度顶点配成 \(m\) 对，并在每一对之间添加一条边，共计添加 \(m\) 条边。（这里允许出现重边，即两个顶点之间可以有多条边。）注意到此时图中所有顶点的度数都变为偶数。由欧拉定理，所得图存在一条 Eulerian tour。移除所添加的 \(m\) 条边后，该游走被拆分为 \(m\) 条 walks，它们共同覆盖原图的所有边，且每条边恰好属于其中一条 walk。

(c) 要证明该命题，需证两个方向：若 \(G\) 是二分图，则它不含奇数长度的 tour；以及若 \(G\) 不含奇数长度的 tour，则它必为二分图。

方向一（二分图 \(\Rightarrow\) 无奇长度 tour）： 设 \(G\) 是二分图，\(L\) 和 \(R\) 是顶点的一个二分划分，使得 \(L\) 内任意两个顶点之间、以及 \(R\) 内任意两个顶点之间都不存在边。再设 \(G\) 中某条 tour 从顶点 \(v_0 \in L\) 开始遍历。

由于 \(G\) 中的每条边都连接 \(L\) 中的一个顶点与 \(R\) 中的一个顶点，该 tour 的第一条边把起点 \(v_0\) 连接到某个顶点 \(v_1 \in R\)。类似地，第二条边把 \(v_1 \in R\) 连接到 \(v_2 \in L\)。一般地，第 \(2k\) 条边把顶点 \(v_{2k-1} \in R\) 连接到 \(v_{2k} \in L\)，第 \(2k+1\) 条边把顶点 \(v_{2k} \in L\) 连接到 \(v_{2k+1} \in R\)。

由于只有偶数编号的边连接到 \(L\) 中的顶点，而我们又从 \(L\) 中的顶点出发，因此该 tour 必定以偶数条边结束。

方向二（无奇长度 tour \(\Rightarrow\) 二分图）： 设 \(G\) 不含奇数长度的 tour。不妨考虑 \(G\) 的某一个连通分支；下述推理可应用于 \(G\) 的所有连通分支。

设 \(v\) 是 \(G\) 中任意一个顶点。我们把 \(G\) 的所有顶点划分到两个不相交的集合中：

\[L = \{u \mid \text{从 } u \text{ 到 } v \text{ 的最短路径长度为偶数}\}\] \[R = \{u \mid \text{从 } u \text{ to } v \text{ 的最短路径长度为奇数}\}\]

我们断言：\(L\) 中任意两个顶点都不相邻。反设存在相邻的顶点 \(u_1, u_2 \in L\)。考虑如下构成的 tour：

• 从 \(v\) 到 \(u_1\) 的最短路径（奇数长度）；

• 边 \((u_1, u_2)\)（长度 \(1\)）；

• 从 \(u_2\) 到 \(v\) 的最短路径（奇数长度）。

该 tour 的长度为奇数，与假设「\(G\) 不含奇数长度的 tour」矛盾。因此 \(L\) 中任意两个顶点都不相邻。

类似地，我们断言：\(R\) 中任意两个顶点都不相邻。反设存在相邻的顶点 \(u_1, u_2 \in R\)。考虑如下构成的 tour：

• 从 \(v\) 到 \(u_1\) 的最短路径（偶数长度）；

• 边 \((u_1, u_2)\)（长度 \(1\)）；

• 从 \(u_2\) 到 \(v\) 的最短路径（偶数长度）。

该 tour 的长度为奇数，与假设矛盾。因此 \(R\) 中任意两个顶点都不相邻。

我们已经证明了：\(L\) 内任意两个顶点之间没有边，且 \(R\) 内任意两个顶点之间也没有边。若 \(G\) 有多个连通分支，同样的划分可应用于所有分支。综上，\(G\) 是二分图。

(a) 由于 \(G\) 是二部图，每条边连接 \(L\) 中的一个顶点与 \(R\) 中的一个顶点。每条边对 \(\sum_{v\in L}\deg(v)\) 与 \(\sum_{v\in R}\deg(v)\) 的贡献相等，因此这两个值必须相等。

(b) 由 (a) 知 \(\sum_{v\in L}\deg(v)=\sum_{v\in R}\deg(v)\)。于是 \(|L|\cdot s=|R|\cdot t\)。稍作代数变形即得 \[\frac{s}{t}=\frac{|R|}{|L|}.\]

(c) 给定一个二部图，将 \(L\) 中所有顶点染成一种颜色，\(R\) 中所有顶点染成另一种颜色，即得到一个 2-染色。反之，给定一个 2-染色图（称两种颜色为红色与蓝色），红色顶点之间没有边相连，蓝色顶点之间也没有边相连。于是取 \(L\) 为红色顶点集，\(R\) 为蓝色顶点集，即构成一个二部划分。因此该图是二部图。