图的曲面嵌入 我们开始学习图的曲面嵌入。这是图论与拓扑学交叉的重要领域，研究图在曲面上的绘制方式，要求边仅在端点处相交。 第一步：从平面图到曲面嵌入的推广 您已经了解了平面图，即可以画在平面上而边不交叉的图。然而，许多图（如完全图K₅或完全二分图K₃,₃）不是平面图。图的曲面嵌入理论将平面图的概念推广到更一般的曲面上。一个图G如果能被画在一个曲面S上，使得其边仅在端点处相交，则称G可嵌入到曲面S中。这样的一个画法称为图G在曲面S上的一个嵌入。平面图就是在球面（与平面拓扑等价）上可嵌入的图。 第二步：曲面的分类与欧拉示性数 理解曲面嵌入，首先要对曲面进行分类。我们主要考虑连通的、紧致的二维曲面（无边界）。这类曲面有一个完整的分类定理：任何这样的曲面都同胚于一个球面，或者带有g个环柄的球面，或者带有k个交叉帽的球面。 可定向曲面 ：其上的方向可以保持一致。例如球面（g=0）、环面（g=1，像一个甜甜圈的表面）、双环面（g=2）等。g被称为曲面的 亏格 。 不可定向曲面 ：最典型的例子是 射影平面 和 克莱因瓶 。它们可以看作是在球面上添加交叉帽得到。 一个关键的不变量是 欧拉示性数 。对于一个将曲面S划分成若干个国家（面）的嵌入图，欧拉公式推广为： χ(S) = V - E + F ，其中V、E、F分别是图的顶点数、边数和曲面被图分割后形成的面数。χ(S)是曲面S本身的拓扑不变量，与图的嵌入方式无关。 对于可定向曲面，χ(S) = 2 - 2g。 对于不可定向曲面，χ(S) = 2 - k（k是交叉帽的个数）。 例如，球面的欧拉示性数为2（对应平面图的欧拉公式），环面的为0，射影平面的为1。 第三步：图在曲面上的嵌入与亏格 对于一个给定的图G，我们关心它所能嵌入的“最简单”的曲面是什么。这就引出了图的亏格参数。 可定向亏格 ：图G的 可定向亏格 ，记作g(G)，是使得G能嵌入到亏格为g的可定向曲面上的最小整数g。平面图的可定向亏格为0。 不可定向亏格 ：图G的 不可定向亏格 ，记作g̃(G)，是使得G能嵌入到亏格为g̃的不可定向曲面上的最小整数g̃。 确定一个图的亏格是NP-困难的，但对于一些特定图类，有明确的公式。例如，完全图Kₙ的可定向亏格为 ⌈(n-3)(n-4)/12⌉ (当n≥3时)，其中⌈⌉是向上取整。这个结果深刻地揭示了图的结构与曲面拓扑之间的内在联系。 第四步：曲面嵌入的对偶图 类似于平面图有对偶图，曲面嵌入的图也有对偶图的概念。给定图G在曲面S上的一个嵌入，我们可以构造其 对偶图G * 。构造方法如下： 在G的每一个面f中放置一个顶点f* 。 对于G的每一条边e，如果它分隔了面f₁和f₂（可能f₁=f₂，如果e是割边），则在f₁ 和f₂ 之间连一条边e* ，且e 与e只相交一次。 对偶图G 也嵌入在曲面S上，并且(G* )* 与G是同构的。对偶概念在研究曲面嵌入的图着色、连通性等问题时非常重要。 第五步：应用与前沿 图的曲面嵌入理论有广泛的应用： 图着色问题 ：著名的Heawood定理（之前是四色定理的推广）指出，任何一个可嵌入亏格为g>0的可定向曲面的图，其色数不超过 ⌊(7+√(1+48g))/2⌋。这解决了可定向曲面上的地图着色问题。 VLSI电路设计 ：在芯片设计中将电路布线在多层板上，可以抽象为图在曲面（或更高维的“厚”曲面）上的嵌入问题，以最小化层数或交叉点。 图的结构性质 ：曲面嵌入限制了图的稠密程度。例如，根据欧拉公式的推论，一个具有n个顶点的图，如果嵌入到亏格为g的曲面上，其边数E = O(n + g)，这表明亏格高的图可以比平面图容纳更多的边。 当前的研究前沿包括研究图在曲面上的唯一嵌入性、嵌入的计数问题、以及在高亏格曲面上的算法复杂性等。