[AGC043E] Topology 题解

这道题把定义都拍到脸上了, 是一个很好的给 OIer 普及什么是拓扑的一个机会. 我将在本文中勾勒出**拓扑学 (topology)** 如何将本题严格地刻画并解决, 但是完整地搬运每一个细节是不必要的, 不如按顺序提及相关的概念, 以便读者从下述书籍中自学: - 尤承业. _基础拓扑学讲义_. - James Munkres. _Topology_. 本文的记号主要和 Munkres 保持一致. 虽然对于解释本题来说并不一定需要, 但是由于是最基础的东西, 我们首先还是明确拓扑空间的定义: > **拓扑空间 (topological space).** 设 $X$ 是一个非空集合, 它的一个子集族 $\mathcal T\subset 2^X$ 需要满足如下条件: > - $\varnothing, X\in \mathcal T$. > - 对任意 $U, V\in \mathcal T$, 有 $U\cap V\in \mathcal T$. > - 对任意 $\{U_{\alpha}\in \mathcal T\}_{\alpha\in J}$, 有 $\bigcup_{\alpha \in J} U_\alpha \in T$. > > 我们称 $X$ 连同其拓扑 $\mathcal T$ 是一个拓扑空间 $(X,\mathcal T)$. $\mathcal T$ 中的元素称为**开集 (open set)**. 对于集合 $D$, 若补集 $X \smallsetminus D$ 为开集, 则称 $D$ 为**闭集 (closed set)**. 这样, 我们平时所说的 $\mathbb R^n$ 上的拓扑所说的开集就是任意多个开球的并. 对于某个子空间 $Y\subset X$, 作为子空间拓扑, $Y$ 上的开集就是全体 $X$ 中的开集与 $Y$ 的交. 此外还可以自然地定义两个拓扑空间的乘积, 使得连续函数的一些复合之类的性质成立, 但接下来讨论里空间总是 $\mathbb R^n$ 的子空间, 所以按下不表. 而连续函数的定义其实在拓扑中反而只用一句话. 我们称 $f\colon X\to Y$ 是**连续 (continuous)** 的, 当且仅当每个 $Y$ 中开集的原像 $f^{-1}(U)$ 是开集. 可以验证, 在分析中 $\mathbb R^n \to \mathbb R^m$ 的连续函数的定义和拓扑学的定义是相容的. 接下来, 题面中所说的闭曲线, 一般的来说就是连续函数 $f\colon [0, 1]\to X$, 我们称其为 $X$ 中的一条**道路 (path)**. 题面所说的从 $C$ 到 $D$ 的连续变化, 更一般地说就是 $C, D\colon X\to Y$ 存在函数 $F\colon X\times [0, 1]\to Y$ 使得 $F(\bullet, 0) = C(\bullet)$ 而 $F(\bullet, 1) = D(\bullet)$. 此时称 $F$ 给出 $C,D$ 间的一个**同伦 (homotopy)**, 容易验证 $F$ 的存在性构成一个等价关系 $C\simeq D$, 称作同伦等价. 对于 $C(0)=C(1)$ 的道路, 这称作一个**回路 (loop)**, 这里值得一提的是, 题面中的定义其实是有问题的! 因为它并没有时刻限制 $F(x, \bullet)$ 是一个回路, 那我们其实就可以先把 $C$ 的一端按照原路返回收缩成一个点, 再让这个点跑到 $D$ 的端点的地方再重新展开, 这样问题就平凡了. 所以这里更加正确的说法是, $C, D$ 是一个 $S^1\to X$ 的连续函数, 这里 $S^1$ 是 $\mathbb R^2$ 上的单位圆, 或者形象地说, 就是将闭区间 $[0, 1]$ 的两端点粘起来. 这样定义下 $C$ 到 $D$ 的同伦才保证了时刻是一个回路而不被拆开. 直接研究 $S^1\to X$ 并不直观, 我们实际上还是得用道路的同伦来进行研究, 但需要加一点限制. 如果两条道路 $C,D$ 的起点和终点相同, 且存在一个 $C$ 到 $D$ 的同伦 $F$, 这个同伦另外保证了 $F(0, \bullet) = C(0)= D(0)$ 和 $F(1,\bullet) = C(1)=D(1)$, 那么这给出 $C$ 到 $D$ 的一个**定端同伦 (path homotopy)**, 可以验证它也给出一个等价关系 $\simeq_p$. 我们接下来记作等价关系 $[C]=[D]$. 定端同伦多出来的一些东西就在于我们可以考虑道路之间的拼接. 对于 $C$ 是从 $x$ 到 $y$ 的道路, $D$ 是从 $y$ 到 $z$ 的道路, 那么 $C*D$ 可以定义为把 $C$ 的这部分放在 $[0, 1/2]$, 把 $D$ 的这部分放在 $[1/2, 1]$, 可以验证, 这给出一个等价类上良定义的运算 $[C]*[D] = [C*D]$, 进一步可以验证这个运算满足结合律. 那么对于一个定点 $x_0$ 到自身的道路来说, 情况就更特殊了, 所有道路之间都可以做运算, 并且 $e(\bullet)=x_0$ 这个常函数满足 $[e]*[C] = [C]*[e] = [C]$. 定义 $\overline {C}$ 为将道路 $C$ 翻转方向, 那么我们又可以验证 $[C]*[\overline C] = [\overline C]*[C] = [e]$, 所以 $x_0$ 到自身的道路的等价类的运算构成一个群! 我们称其为**基本群 (fundamental group)**, $\pi_1(X,x_0)$. 对于题目中给定的点集 $S = \{(i+0.5, 0.5) \mid 0\leq i < n\}$, 我们规划的路径必然对应为 $\mathbb R^2 \smallsetminus S$ 的一个基本群里的一个元素. 我们首先要搞清楚其基本群的结构是长啥样的 (这样才明白这道题的 spj 是怎么写的). 为此, 我们需要有一些基本的工具来对一个拓扑空间进行一些处理. 一个比较基本的手段就是发掘一个拓扑空间的 **(强) 形变收缩核 ((strong) deformation retract)**. 这是说一个拓扑空间 $X$ 如果有一个子空间 $A$, 且 $id(x) = x$ 到一个连续函数 $r\colon X\to A$ 是同伦的, 且这个同伦满足对任意 $a\in A, t\in [0, 1]$, 有 $H(a, t) = a$, 此时就称 $A$ 是 $X$ 的一个强形变收缩核. 容易发现, 这个同伦能够把任何一个基本群中的元素 $[f] \in \pi_1(X,a_0)$ 同伦到 $[r\circ f] \in \pi_1(A, a_0)$, 而且进一步给出了二者之间的一个同构.  如上图 (摘自 James Munkres, _Topology_) 所示, 这给出了一个 $\mathbb R^2$ 挖去两个点后, 可以强形变收缩到两个环粘起来, 写作 $S^1 \vee S^1$. 不难想象, 挖去 $n$ 个点后, 可以强形变收缩成将 $n$ 个环经由同一个点粘起来的结构, 记该交点为 $b_0$, 我们只需要研究 $\pi(S^1 \vee \dots \vee S^1, b_0)$ 的结构即可. **复叠空间 (covering space)** 的理论可以比较轻易地说明 $\pi_1(S^1, b_0)$ 是无限循环群 $\mathbb Z$, 且由在它上面"走一圈"的回路作为生成元 $1$. 而 **van Kampen 定理** 可以帮助我们处理确定将拓扑空间进行粘合的时候基本群的结构. 以 $X=S^1 \vee S^1$ 为例子, 选取两个环上各一个点 $p_1, p_2$, 那么 $A=X \smallsetminus \{p_1\}$ 和 $B=X \smallsetminus \{p_2\}$ 各自可以强形变收缩成一个环, 基本群是 $\mathbb Z$. 它们的交集 $A\cap B = X \smallsetminus \{p_1, p_2\}$ 可以强形变收缩成一个点, 是单连通的. 对于这种情况, van Kampen 定理断言 $X= A\cup B$ 在 $b_0$ 的基本群是 $A$, $B$ 各自在 $b_0$ 基本群的**自由积 (free product)** $\mathbb Z * \mathbb Z$. 顾名思义, 两个群的自由积就是我们希望将它们最为自由地乘起来, 除了他们群里各自的单位元都是得到的群的单位元. 具体地说, $G = G_1 * G_2$ 里的每个元素有一个唯一的**既约字 (reduced word)** 表示 $x_1 x_2 \dots x_m$, 其中每个 $x_i \in G_1 \cup G_2 \smallsetminus \{1\}$, 且相邻的 $x_i$ 不能属于同个群. 两个字的乘法就是将它们首尾相连, 然后相邻属于同个群的都按照定义做运算, 得到 $1$ 则去掉, 以此类推. 证明这个构造确实成群只是琐事, 不过也有略聪明些的方法简化步骤. 进一步地, 我们可以得到那 $n$ 份环粘起来 $S^1 \vee \dots \vee S^1$ 在 $b_0$ 的基本群是 $n$ 份 $\mathbb Z$ 的自由积, 也称作 $n$ 个元素的**自由群 (free group)**, 而且收缩得到的 $n$ 个环各自对应于一个元素. 也就是说, 群的结构无非就是 $\{x_1, x_1^{-1}, x_2, x_2^{-1},\dots, x_n, x_n^{-1}\}$ 组成的字符串, 且相邻两项不为逆. 直观上看就是, 要消除之前走的路的影响, 仅能通过"原路返回"做到. 这里要注意的是, $\mathbb R^2 \smallsetminus S$ 的强形变收缩核有很多种选取方式, 如前面的图中, 我们也可以选取一个环包住 $p$, 另一个环同时包住 $\{p, q\}$, 由于 $S^1 \vee S^1$ 不在意这里的包含关系, 我们同样得到了一组生成元, 但是这组生成元和图中 8 字形的两个环的两个回路并不能一一对应. 从代数角度来说, 就是 $\{x,y\}$ 生成的自由群同样可以被 $\{x, xy\}$ 自由地生成. 为明确结构, 我们接下来假设的是选取了一个每个点恰被一个环包住一圈的情况, 可以想象成"开花". 对于 $T\subset S$, 有嵌入 $\iota\colon \mathbb R^2 \smallsetminus S \to \mathbb R^2 \smallsetminus T$, 自然地给出一个基本群的态射 $\iota^* \colon \pi_1(\mathbb R^2 \smallsetminus S, x_0) \to \pi_1(\mathbb R^2 \smallsetminus T,x_0)$, 无非都是某个 $[f]$, 容易验证连续映射给出了一个基本群之间的**群同态 (group homomorphism)**. 接下来我们用 $i$ 指代 $S$ 中的第 $i$ 个点. 容易验证, 如果 $i\notin T$, 那么 $\iota^*$ 把 $x_i$ 映到单位元, 而对于 $i\in T$, 这些 $\iota^*(x_i)$ 自由地生成了 $\mathbb R^2 \smallsetminus T$ 的基本群. 至此, 我们完全将这个问题转化成了一个明确的代数问题: > 试找出一个自由群 $\mathbf F(x_1,\dots,x_n)$ 中的元素 $w$, 使得对于每个 $T\subset S$, 忽略 $S\smallsetminus T$ 中元素的同态 $\phi_{S\to T}$ 按照所给的要求将 $w$ 映到单位元或非单位元. --- 显然我们有问题有解一些必要条件, 首先去掉所有点之后群是平凡的, 所以我们一定会有 $\phi_{S\to \varnothing} (w) = 1$. 此外, 有 $\phi_{S\to T} = \phi_{R\to T} \circ \phi_{S\to R}$, 所以对于 $T\subset R$, $\phi_{S\to R}(w)=1$ 就必有 $\phi_{S\to T}(w) = 1$. 通过这样的封闭性检验是个必要条件. 然后呢? 我们很容易知道 $w=x_1x_2\dots x_n$ 可以让所有非空集合 $T$ 都有 $\phi_{S\to T}(w)\neq 1$, 但一般情况呢? 先考虑 $n=2$ 时的一个非平凡情况, 如果 $\phi_{S\to T}(w)=1 \iff T \neq S$, 我们有这样的构造吗? 实际上是有的: $xyx^{-1}y^{-1}$. 这被称为两个元素的**交换子 (commutator)** $[x,y]$. 我们可以借此构造一个更一般一点的情况, 记 $w_{x} = x$, $w_{x, T} = [x, w_T]$, 我们可以发现 $\phi_{S\to T}(w_S) \neq 1$ 当且仅当 $T= S$. 这是容易归纳验证的, 只需利用 $\phi(w_{x, T}) = [\phi(x), \phi(w_T)]$ 这一性质, 若 $R\neq S$, 则失去至少一个元素, 如果 $x\notin R$, 那 $[\phi(x), \phi(w_T)] = [1, \phi(w_T)] = 1$, 否则失去的元素在 $T$ 里, 归纳有 $[\phi(x), \phi(w_T)] = [\phi(x), 1] = 1$. 最后我们可以考虑对剩下的所有情况做出构造了. 我们取出所有极小的规定了 $\phi_{S\to R}(w)\neq 1$ 的 $R$. 将这些所有 $R$ 的 $w_R$ 相乘, 我们验证它满足我们的要求. 对于 $T$, 显然 $\phi_{S\to T}$ 消去了所有不是 $T$ 的子集的 $R$. 当 $\phi_{S\to T}(w)\neq 1$, 必有至少一个 $R$ 是 $T$ 的子集, 我们只需证明多个这样的 $w_R$ 相乘不为 $1$, 直接利用 $R$ 的极小性条件, 任取一个 $R$, 必有 $\phi_{S\to R}(w) = w_R \neq 1$, 因此在 $T$ 上也不为 $1$. 这种递归构造的字长为 $T(n) = 2T(n-1) + 2$, 因此 $T(n) = O(2^n)$, 所有 $w_R$ 的串长加起来不超过 $O(3^n)$, 由于一个回路实际上输出可能需要 $O(n)$ 的长度, 路径的长度是 $O(n3^n)$ 的, 并且可以通过. 不过值得一提的是, 有复杂度更低的构造. 我们将交换子的利用方法改成均匀的砍两半, 也就是 $w_{L,R} = [w_L, w_R]$, 这样递归式就是 $T(n) = 4T(n/2)$, 有 $T(n) = O(n^2)$, 串长加起来不超过 $O(n^{1.5} 2^n)$ (Sperner 定理说明最多有 $\binom{n}{\lfloor n/2\rfloor}$ 个极小集合, Stirling 近似公式说明这个数是 $O(n^{-0.5}2^n)$.), 路径长度有上界 $O(n^{2.5} 2^n)$. --- 前面提到的 $\binom{n}{n/2}=\Theta(n^{-0.5}2^n)$ 也能帮我们直接给出单调布尔函数数量的一个下界, 这说明我们的构造在最坏情况已经指数上做到最优了. 说句题外话, [Erik Demaine 等人的工作](https://arxiv.org/abs/1203.3602)进一步总结了将布尔函数做 $\textbf{AND}$, $\textbf{OR}$ 时候对应的一些构造, 并讨论了一些相关的问题, 有兴趣的同学可以延伸阅读一下.