[AGC043E] Topology 题解

· · 题解

这道题把定义都拍到脸上了, 是一个很好的给 OIer 普及什么是拓扑的一个机会.

我将在本文中勾勒出拓扑学 (topology) 如何将本题严格地刻画并解决, 但是完整地搬运每一个细节是不必要的, 不如按顺序提及相关的概念, 以便读者从下述书籍中自学:

本文的记号主要和 Munkres 保持一致.

虽然对于解释本题来说并不一定需要, 但是由于是最基础的东西, 我们首先还是明确拓扑空间的定义:

拓扑空间 (topological space). 设 X 是一个非空集合, 它的一个子集族 \mathcal T\subset 2^X 需要满足如下条件:

  • 对任意 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 等人的工作进一步总结了将布尔函数做 \textbf{AND}, \textbf{OR} 时候对应的一些构造, 并讨论了一些相关的问题, 有兴趣的同学可以延伸阅读一下.