图的亏格与嵌入曲面
好的，我们将开始学习一个新的图论词条：图的亏格与嵌入曲面。这个概念将图的可平面性推广到了更一般的曲面之上，是拓扑图论中的一个核心内容。
第一步：从平面图到曲面——为什么要推广？
首先，我们回顾一个你已经了解的概念：平面图。如果一个图可以画在平面上，使得它的边仅在顶点处相交，那么我们称这个图是平面图。
然而，许多重要的图并不是平面图。最著名的例子是完全图 \(K_5\) 和完全二分图 \(K_{3,3}\)。根据库拉托夫斯基定理，一个图是平面图当且仅当它不包含 \(K_5\) 或 \(K_{3,3}\) 的细分。
这就引出了一个自然的问题：对于那些非平面图，我们能否通过改变“画图的空间”来避免边的交叉呢？答案是肯定的。我们可以将图嵌入到更复杂的曲面上，比如球面、环面（形状像一个甜甜圈）或者更高“孔数”的曲面上。图的亏格就是用来衡量一个图需要多复杂的曲面才能实现“无交叉”嵌入的拓扑参数。
第二步：理解曲面——拓扑学中的“可定向曲面”
为了精确定义亏格，我们需要先理解我们要嵌入的“曲面”是什么。在拓扑图论中，我们主要关注的是紧致可定向曲面。
- 球面 (Genus 0)：这是最简单的曲面。任何一个平面图都可以嵌入到球面上（想象一下通过球极投影，平面和球面之间可以建立联系）。
- 环面 (Genus 1)：形状像一个甜甜圈表面。在环面上，我们可以无交叉地嵌入 \(K_5\) 和 \(K_{3,3}\)。
- 双环面 (Genus 2)：可以想象为有两个洞的曲面。更复杂的图可能需要嵌入到这样的曲面上。
一个曲面的亏格 (Genus of a Surface)，记作 \(g\)，直观上就是该曲面所包含的“洞”的个数。球面的亏格是0，环面的亏格是1，双环面的亏格是2，以此类推。
关键点：所有可定向曲面都可以由球面附着上若干个“环柄”来得到。每个环柄贡献一个“洞”，即增加亏格1。
第三步：定义图的亏格
现在，我们将曲面的亏格概念与图联系起来。
一个图 \(G\) 的可定向亏格 (Orientable Genus)，通常简称为亏格，记作 \(\gamma(G)\) 或 \(g(G)\)，定义为能够无交叉地嵌入 \(G\) 的所有可定向曲面中，亏格最小的那个曲面的亏格。
用更正式的语言说：
\[ \gamma(G) = \min\{g \geq 0 \mid G \text{ 可以嵌入到亏格为 } g \text{ 的可定向曲面上} \} \]
例子：
- 树或任何平面图：它们可以嵌入到球面（亏格0）上，所以它们的亏格 \(\gamma(G) = 0\)。
- 完全图 \(K_5\)：它不是平面图（不能嵌入球面），但可以嵌入环面（亏格1）。而且，它不能嵌入任何亏格小于1的曲面（即球面）。因此，\(\gamma(K_5) = 1\)。
- 完全图 \(K_7\)：它是一个更复杂的图，需要至少亏格为3的曲面才能实现无交叉嵌入。因此，\(\gamma(K_7) = 3\)。
第四步：一个关键的等价视角——多面体表示与欧拉公式
如何判断一个图能否嵌入某个亏格的曲面？一个强大的工具是推广的欧拉公式。
对于平面图，我们有经典的欧拉公式：对于一个连通的平面图，有 \(V - E + F = 2\)，其中 \(V\) 是顶点数，\(E\) 是边数，\(F\) 是面数（包括那个无限大的外部面）。这里的“2”正好是球面的欧拉示性数。
当图嵌入到亏格为 \(g\) 的可定向曲面上时，欧拉公式被推广为：
\[ V - E + F = 2 - 2g \]
这里，\(g\) 就是曲面的亏格。
这个公式极其有用。如果我们能找到一个嵌入，并且数出它的面数 \(F\)，那么我们就可以通过公式 \(g = \frac{1}{2}(2 - V + E - F)\) 来计算这个嵌入所在的曲面的亏格。而图的亏格，就是所有可能的嵌入中，计算出的 \(g\) 的最小值。
此外，如果我们知道图是2-胞腔嵌入的（即嵌入的每个面都同胚于一个圆盘），那么我们可以利用这个公式来推导出图亏格的下界。例如，因为每个面至少由3条边围成（假设是简单图），且每条边最多属于2个面，所以有 \(3F \leq 2E\)。将这个不等式代入广义欧拉公式，可以得到：
\[ \gamma(G) \geq \left\lceil \frac{E}{6} - \frac{V}{2} + 1 \right\rceil \]
这是一个计算图亏格下界的实用工具。
第五步：计算图的亏格——挑战与已知结论
确定一个任意图的亏格是一个计算难度极高的问题。它已经被证明是 NP-难 的。这意味着没有已知的多项式时间算法能解决所有图的亏格计算问题。
尽管如此，数学家们已经成功计算出了许多重要图族的准确亏格。
- 完全图 \(K_n\)：其亏格由一个经典的公式给出（\(n \geq 3\)）：
\[ \gamma(K_n) = \left\lceil \frac{(n-3)(n-4)}{12} \right\rceil \]
这个公式由 Ringel 和 Youngs 在1968年证明，是拓扑图论的一项里程碑式成就。
- 完全二分图 \(K_{m,n}\)：
\[ \gamma(K_{m,n}) = \left\lceil \frac{(m-2)(n-2)}{4} \right\rceil \]
- n-维立方体图 \(Q_n\)：对于 \(n \geq 2\)，有 \(\gamma(Q_n) = 1 + 2^{n-3}(n-4)\)。
对于不属于这些特定族的一般图，研究通常集中于寻找好的亏格上下界，或者设计实用的算法来测试一个图能否嵌入低亏格曲面（如平面性测试算法被推广到测试环面嵌入性）。
总结
- 图的亏格 \(\gamma(G)\) 是图的一个拓扑不变量，它衡量了图在可定向曲面上实现“无交叉”绘制所需曲面的最小复杂度（以“洞”的个数衡量）。
- 它是平面图概念的推广：平面图是亏格为0的图。
- 广义的欧拉公式 \(V - E + F = 2 - 2g\) 是理解和计算亏格的核心工具。
- 确定图的亏格是困难的（NP-难问题），但对于完全图、完全二分图等重要图类，我们有精确的公式。
通过理解图的亏格，我们将图的结构与其拓扑性质深刻地联系了起来，这是图论与拓扑学交叉融合的一个优美范例。