图的平面嵌入唯一性与惠特尼定理 我们先从直观理解开始。 平面图是可以在平面上画成无交叉边的图。但同一个平面图可能有多种“看起来不同”的平面画法，这引出“平面嵌入”的概念：一个画在平面上使得边只在端点相交的具体布局。 第一步：平面嵌入的定义与等价 严格来说，一个 平面嵌入 是一个从图到平面的映射，将顶点映为不同的点，边映为不交叉的连续曲线（除端点外）。 两个平面嵌入 拓扑等价 ，如果存在平面的一个自同胚（连续可逆映射），把一个嵌入的顶点和边映射到另一个嵌入对应的顶点和边上。 等价意味着它们的面（被边划分的区域）一一对应，且面的边界圈相同。 第二步：平面图的嵌入不唯一 看一个例子：三角形（3个顶点的完全图 \(K_ 3\)）在平面上只有一种平面嵌入（一个三角形面和一个外面）。 但对于一个更复杂的平面图，比如一个四边形加一条对角线，不同的嵌入可能改变外部的面是哪个。 不过，在球面上，任何面都可以作为外部面，所以如果考虑 球面嵌入 ，则平面嵌入的外部面选择不影响拓扑类型，只要重新定义投影点即可。 第三步：2-连通与嵌入唯一性 关键观察 ：如果一个图是 1-连通（连通但有关割点），我们可以把各个块（极大 2-连通子图）在割点处旋转，得到不同的平面嵌入。 所以唯一性通常对 2-连通图讨论。 定理（惠特尼，1932） ： 一个 2-连通的平面图（顶点数 ≥ 3）的平面嵌入在球面意义下是唯一的，当且仅当它是 3-连通的。 这里 3-连通意味着删除任意 2 个顶点后图仍连通（且顶点数 > 3）。 第四步：唯一性的含义与对偶 “唯一”意味着：这个图的任何两个平面嵌入，其面的边界集合相同（可能次序不同，但作为圈集合一样）。 对偶图也唯一确定。 为什么 3-连通是必要且充分的？ 直观原因： 如果一个 2-连通但不是 3-连通的图，存在一个 2-顶点割 \(\{u,v\}\)，图可以分解成两个部分只通过不相交的 \(u\)–\(v\) 路径连接，那么可以“翻转”其中一个部分，得到另一个不等价的嵌入。 如果是 3-连通，没有 2-顶点割，就没有这种翻转的可能，因此嵌入唯一。 第五步：惠特尼定理的推广 对 2-连通但非 3-连通的平面图，不同的嵌入数目可以通过分解为“三连通组件”来研究，这联系到图的“SPQR 树”结构——每个 3-连通组件是唯一的，但组合方式可翻转。 第六步：算法意义 平面嵌入唯一性对画图、电路板布局、拓扑图算法有影响。例如，唯一嵌入的图其对偶唯一，在平面图上的某些计数问题变得简单。 判定一个平面图是否有唯一平面嵌入可在多项式时间完成（通过分解为 3-连通分支检查）。 第七步：扩展概念 外平面嵌入唯一性：所有顶点在外面的嵌入，唯一性条件不同。 有向平面嵌入唯一性：考虑边的旋转顺序固定下的不同嵌入。 如果你已清楚以上，我们可以继续进入“图的平面嵌入唯一性”相关的算法（如唯一性测试）、与“图的平面编码”（如平面编码唯一性）的联系。是否需要深入某个具体方向？