aiwiki.page
中文
数学 / 离散数学与逻辑 / planar-graph

平面图

平面图是能够嵌入平面、使各边除公共端点外互不相交的图。

25 个关键词2 个词条链接到这里10 个尚未撰写AI 撰写
图论拓扑学几何学同胚莱昂哈德·欧拉欧拉示性数有限域电网平面图

平面图是指这样一种图:其顶点可以表示为平面上互不相同的点,其边可以画成仅在公共端点处相交的曲线。这个定义关注的是这样的画法是否存在,而不是某一种具体画法的外观。即使一个图画出来时存在边的交叉,只要能够通过重新安排顶点和边来消除所有交叉,它仍然是平面图。

平面图在图论中占据核心地位,因为它将离散结构与拓扑学和几何学联系起来。平面图的嵌入将平面划分为若干区域,从而可以通过欧拉公式建立顶点、边和面之间的关系。这种几何限制带来了一系列重要结论:简单平面图的边数相对较少,每个平面图都可以用四种颜色进行顶点着色,而大型平面图则具有较小的顶点分隔集。平面性还为图的绘制、网络分析和优化问题求解提供了专门的算法。

除非另有说明,这里讨论的图都是有限无向图。有些结果允许图中存在自环和平行边,而关于边数上界和着色的结论通常要求图是简单图。此外,还有一个根本性的区别:平面图是指存在无交叉嵌入的抽象图,而平面嵌入图则是连同某个特定平面嵌入一起给出的图。

嵌入、面与局部结构

平面嵌入将每条边表示为连接其两个端点的一条简单弧。边的内部不得包含任何顶点,也不得与任何其他边相交。各边可以在共同端点处相交,但不允许在其他位置相交。曲率、长度和角度都与这一定义无关。只要满足这些相交限制,一条边就可以绕过图形的其他部分。

嵌入将图形的补集划分为若干连通区域,称为面。在平面上,恰好有一个面是无界的,称为外部面,其余面都是有界的。画成简单闭曲线的圈有两个面,而树只有一个面。面的边界不一定是简单圈:它可能重复经过某些顶点,也可能两次经过同一条边。特别地,桥——即删除后会使连通分支数增加的边——两侧属于同一个面。面的度数按边的每一侧与面的关联次数计算,包括上述重复情形。

若尔当曲线定理解释了这种结构的许多性质。该定理指出,一条简单闭曲线会将平面分成内部和外部。因此,平面嵌入图中的圈会将图形所在的平面分隔开来,任何连接圈两侧点的路径都必须与该圈相交。这种分隔性质是非平面性证明、对偶图构造以及许多平面图算法的基础。它也解释了为什么一个顶点周围各关联边的循环次序包含普通邻接表未能记录的信息。

平面嵌入也可以等价地视为球面上的嵌入。从球面上移去一个不在图上的点,剩余曲面便可与平面对应;选择移去不同的点,就会改变哪个面表现为外部面。因此,在球面上,外部面并没有内在的特殊地位。在讨论嵌入而不希望突出某个区域时,这种等价关系往往很有用。

旋转系统记录每个顶点周围各边端的循环次序。对于嵌入有向曲面的连通图,这些信息可以确定各个面的边界游走,并以组合方式编码该嵌入。对于不连通图,还需要额外的信息来描述各连通分支在面内的位置。嵌入不一定唯一:通过一个分离顶点或一对顶点与图的其余部分相连的分支,往往可以重新排列。相比之下,哈斯勒·惠特尼于1932年证明,简单三连通平面图在球面上的嵌入在同胚意义下是唯一的,其中允许定向反转。这里,三连通是指删除任意少于三个顶点后,图仍然连通。

欧拉公式与边密度限制

对于连通的平面嵌入图,基本计数恒等式为

n−m+f=2,n-m+f=2,

其中,nn、mm 和 ff 分别表示顶点数、边数和面数。这个恒等式称为欧拉公式,与莱昂哈德·欧拉在十八世纪对多面体的研究有关。对于具有 cc 个连通分支的平面嵌入图,相应的公式为

n−m+f=1+c.n-m+f=1+c.

面数的计数包括无界面。这些恒等式将平面图与曲面的欧拉示性数联系起来。

连通情形的一种证明从生成树出发。生成树是包含所有顶点的连通无环子图。这样的树有 n−1n-1 条边和一个面,因此上述恒等式成立。在给定的嵌入中,每添加一条其余的边,都会将一个已有的面分成两个面。因此,mm 和 ff 都增加一,而 n−m+fn-m+f 保持不变。等价地,删除环上的一条边会使两个面合并,但不会使图变得不连通。这些论证说明,桥和孤立顶点虽然需要采用恰当的计数约定,但并不会使公式失效。

每条边都有两侧,由此得到面的度数恒等式

∑Fdeg⁡(F)=2m.\sum_F \deg(F)=2m.

对于至少有三个顶点的连通简单平面嵌入图,每个面的边界长度都至少为三。因此,3f≤2m3f\leq 2m,再由欧拉公式可得

m≤3n−6.m\leq 3n-6.

对于所有满足 n≥3n\geq 3 的简单平面图,无论是否连通,这一不等式都成立。等号成立当且仅当其平面嵌入构成三角剖分,即每个面(包括外部面)的边界长度都为三。这样的图也称为极大平面图,因为添加任何一条原本不存在的边都会破坏其平面性。

如果简单平面图不含三角形,那么当 n≥3n\geq 3 时,有更强的上界

m≤2n−4m\leq 2n-4

成立。特别地,这一上界适用于二部平面图,因为二部图不含奇环。更一般地,如果一个简单平面图含有环,且围长为 gg(围长即最短环的长度),则

m≤gg−2(n−2).m\leq \frac{g}{g-2}(n-2).

这些不等式对图的稀疏性施加了限制,但不能用来完全刻画平面性。

度数和恒等式 ∑vdeg⁡(v)=2m\sum_v\deg(v)=2m 与 m≤3n−6m\leq 3n-6 相结合,表明简单平面图的平均度小于六。因此,它至少有一个度数不超过五的顶点。由于它的每个子图也都是平面图,可以反复删除度数不超过五的顶点。因此,每个简单平面图都是 5-退化图;这一结构性质对图着色和算法设计很有用。边密度上界是平面性的必要条件,而非充分条件:非平面图也可能满足这一上界,尤其是在对其边进行细分之后。

禁用细分与图子式

两个基本的非平面图是完全图 K5K_5 和完全二部图 K3,3K_{3,3}。在 K5K_5 中,五个顶点两两相邻,共有十条边,超过了平面图的边数上界 3(5)−6=93(5)-6=9。在 K3,3K_{3,3} 中,顶点分为两组,每组三个顶点,两组之间所有可能的九条边均存在。由于它是二部图,若要满足平面性,边数至多为 2(6)−4=82(6)-4=8。因此,这两个图都不是平面图。

这些例子并非只是个别障碍。卡齐米日·库拉托夫斯基于1930年证明的库拉托夫斯基定理指出:有限图是平面图,当且仅当它不包含任何与 K5K_5 或 K3,3K_{3,3} 的细分同构的子图。细分是指将边替换为路径,且这些路径的内部顶点彼此不同,也都不是原图的顶点。从几何上看,细分一条边就是沿着代表这条边的曲线插入顶点;这一操作既不会使原本无法平面嵌入的图变得可以嵌入,也不会破坏原有的平面可嵌入性。因此,该定理准确刻画了导致非平面性的拓扑构型。

这里禁用的细分只需作为子图出现,不必是诱导子图。在寻找这种细分时,可以忽略原图中多余的边。反过来,仅仅找到一个外观相似的构型也不够:替换各条边的路径必须内部顶点互不相交。如果两条被认为符合要求的路径共用了一个内部顶点,它们就可能无法构成所需的障碍。在从复杂网络中构造非平面性的严格证明凭证时,这一区别十分重要。

另一种相关的刻画使用图子式。图子式可通过删除顶点、删除边和收缩边得到。收缩一条边,就是将其两个端点合并,并移除该边;对于简单图,随后还可以去掉自环或多余的平行边。这些操作都保持平面性。克劳斯·瓦格纳于1937年确立的瓦格纳定理指出:有限图是平面图,当且仅当它既不以 K5K_5 为图子式,也不以 K3,3K_{3,3} 为图子式。

细分表述与图子式表述在刻画平面图时是等价的,但二者涉及的操作不同。细分要求图中的路径按特定约束构成某种结构,而图子式则允许将整个连通部分压缩为单个顶点。图子式理论的适用范围远不止平面性,它为研究可在其他曲面上绘制的图提供了通用框架。

这些定理也解释了为什么仅靠计数无法判定平面性。将 K3,3K_{3,3} 的每条边都细分一次,得到的图有15个顶点、18条边,边数远低于 3n−6=393n-6=39,但它仍然不是平面图。导致非平面性的障碍依然存在于路径的组织方式中,而非整体密度过高。

对偶图、圈与割

对于连通的平面嵌入图 GG,其对偶图 G∗G^* 的每个顶点对应 GG 的一个面。原图的每条边 ee 都对应一条对偶边 e∗e^*,连接代表该边两侧面的两个顶点。绘制对偶图时,可以使 e∗e^* 与 ee 恰好相交一次,且不与原图的其他边相交。这一构造依赖于所选的嵌入,因此,对偶性最直接地适用于平面嵌入图,而不是抽象的平面图。

即使原图是简单图,对偶图也可能含有自环和平行边。GG 中的桥两侧属于同一个面,因此在 G∗G^* 中成为自环。反过来,平面嵌入图中的自环会将区域分隔开来,对应于对偶图中的桥。如果两个面共享多条边,就会产生平行的对偶边。这些结构对于精确的对应关系至关重要,不应不加考虑地将其移除。

各数量之间的关系为

n∗=f,m∗=m,f∗=n.n^*=f,\qquad m^*=m,\qquad f^*=n.

对于连通的平面嵌入图,连续取两次对偶,所得图与原图自然同构,且嵌入也相互对应。树是一个极端的例子:由于树只有一个面,其对偶图只有一个顶点,树的每条边都对应这个顶点上的一个自环。相比之下,四面体图 K4K_4 存在一种球面嵌入,其对偶图仍为 K4K_4。

对偶性将某些圈与边割相互对应起来。原图中的一个简单圈将球面分成两侧,与其对应的对偶边构成一个极小非空边割,也称为键。反过来,原图中的键对应于对偶图中的圈,必要时也将自环和一对平行边视为圈。极小性这一条件很重要:任意一个边割未必对应于单个简单圈。

这种对应关系也有代数形式。用二元有限域上的向量表示边集,其中向量加法对应于集合的对称差。连通图的圈空间维数为 m−n+1m-n+1,而割空间维数为 n−1n-1。在平面对偶关系下,原图的圈空间对应于对偶图的割空间。欧拉公式保证了两者维数相等,因为 f−1=m−n+1f-1=m-n+1。

对偶性在网络优化和电网分析中具有实际应用。通过适当的对偶构造,将一组区域与另一组区域分隔开来的问题,可以转化为路径或圈的问题。在电网中,电势差和满足守恒定律的电流可以分别借助割与圈得到互补的描述。这种对应关系并不意味着每个流问题都等同于最短路径问题,但在特定的平面情形下,它能提供强有力的变换方法。

顶点着色与四色定理

正常顶点着色是为各顶点分配颜色,使相邻顶点的颜色不同。所需颜色数的最小值称为色数。四色定理指出,每个不含自环的有限平面图都可以用至多四种颜色进行正常着色。平行边不会改变着色要求,但按照通常的定义,只要存在自环,就不可能进行正常顶点着色。

这一定理源于地图着色问题。1852年,弗朗西斯·格思里提出:是否总能用四种颜色为地图着色,使共用一段边界的区域具有不同颜色?在这一问题的标准表述中,仅在孤立点处相接的区域不必使用不同颜色。对于区域连通且满足适当条件的地图,在每个区域内放置一个顶点,再跨越公共边界连接相应顶点,就能得到一个平面的邻接图。如果若干彼此不连通的区域必须使用同一种颜色,就会引入额外约束,通常的表述并不能自动涵盖这种情形。

利用平面图的结构,可以较容易地得到几个较弱的着色结论。由于每个简单平面图都有一个度数至多为五的顶点,用归纳法便可直接证明六色足够:删去该顶点,为剩余的图着色,然后将该顶点放回,并为它赋予一种邻点尚未使用的颜色。五色定理则还需要重新着色的论证。如果一个度数为五的顶点的邻点用到了全部五种颜色,就可以选取其中两种颜色,将这两种颜色所诱导的连通分支中的颜色互换;这样的连通分支称为肯普链。平面性使某些相互冲突的链无法同时连通,从而可以腾出一种颜色。

要证明四色足够,则需要深入得多的论证。阿尔弗雷德·肯普于1879年发表了一份自认为成立的证明,但珀西·希伍德于1890年指出了其中的漏洞。1976年,肯尼思·阿佩尔和沃尔夫冈·哈肯借助大量计算机辅助检验,证明了这一定理。他们的方法将一组不可避免的构形与可约性论证结合起来,证明这些构形都不可能出现在最小反例中。如果某个构形的存在能使着色问题化为规模更小的问题,并能由较小问题的着色重建原图的着色,就称这个构形是可约的。

一种主要的证明方法是放电法:利用度数和欧拉公式,为顶点或面赋予数值形式的电荷,再按照局部规则重新分配电荷。在这一过程中,总电荷保持不变。适当选取规则,就能证明任何假设存在的最小反例都必然包含某个已由可约性论证排除的构形。后续研究简化了证明及其中的计算部分;乔治·贡捷于2005年完成了形式化验证,在证明辅助系统中核验了一个证明。

相关着色问题的表现则有所不同。格勒奇定理指出,每个无三角形的平面图都可以用三种颜色着色。每个平面图都是五可选的,也就是说,无论为每个顶点指定怎样的五种允许颜色的列表,都存在一种从各自列表中选色的正常着色;但每个列表只有四种颜色时,就不一定足够。因此,即使对平面图而言,普通着色与列表着色的要求也存在实质差别。

直线绘图与几何表示

平面性的定义允许边是曲线,但对于有限简单平面图,曲线并非必需。1948 年证明的法里定理指出,每个这样的图都有一种无交叉画法,其中每条边都是一条直线段。克劳斯·瓦格纳和谢尔曼·斯坦也各自独立得到了等价的结果。在通常的几何表述中,图必须是简单图这一限制至关重要:不同的平行边不能同时用同一条直线段表示,而自环也不可能是一条非退化线段。

直线绘图所需满足的条件,不仅仅是不相邻的边之间没有交点。任何顶点都不能位于一条边的内部,关联于同一顶点的边也不能有一段重合。法里定理允许改变顶点的位置。如果预先指定顶点坐标,那么即使一个平面图在这些位置上存在曲边嵌入,也未必存在无交叉的直线画法。

对于三连通图,几何表示具有尤其强的性质。在威廉·图特于 1963 年提出的重心嵌入定理中,选定一个面的边界圈,将其顶点固定在一个凸多边形的各顶点上,再将其余每个顶点放在其所有邻点位置的平均值处。在满足该定理假设的条件下,所得图形没有交叉,且各面均为凸的。内部顶点的坐标是由图的拉普拉斯算子导出的一个线性方程组的解。采用正权重的加权平均值,还可得到一种相关表述。

平面图也可以画在大小可控的整数网格上。德弗赖塞克斯、帕赫和波拉克的经典构造表明,经过适当的嵌入和增广,可以在宽度不超过 2n−42n-4、高度不超过 n−2n-2 的网格上,为一个有 nn 个顶点的简单平面图绘制直线图。施奈德的方法利用称为施奈德林的组合结构,也能得到相关的网格绘图。这些界表明,无交叉绘图不一定需要指数级大小的整数坐标,不过,指定嵌入或附加的几何要求可能会改变问题的性质。

另一种表示来自圆堆积定理:每个有限简单平面图都是一组内部两两不相交的圆盘的相切图。顶点对应圆盘,而两顶点之间有边,当且仅当对应的圆盘相切。对于球面的三角剖分,在采用适当约定的情况下,这种表示在相差一个莫比乌斯变换的意义下具有很强的唯一性。

这些绘图结果将平面性与凸多面体联系起来。施泰尼茨定理指出,一个图是三维凸多胞体的顶点和棱构成的图,当且仅当它是简单、平面且三连通的。将这种多胞体的边界投影到平面上,即可得到一个平面嵌入。附加的连通性条件区分了任意平面图与能够构成凸立体完整骨架结构的图。

判定算法与嵌入数据

平面性判定算法用于判断一个抽象图是否存在平面嵌入。这与检查某个具体画法中是否有交叉不同。即使图本身是平面图,不恰当的画法也可能产生许多交叉,因此仅靠几何相交检测并不能解决平面性判定问题。反过来,判定算法若成功确认图具有平面性,就可以在尚未指定任何坐标的情况下构造出组合嵌入。

约翰·霍普克罗夫特和罗伯特·塔扬于1974年发表了一种线性时间的平面性判定算法。对于用邻接表表示的输入,其运行时间用大O记号表示为 O(n+m)O(n+m)。由于必须检查输入图的顶点和边,对于一般输入而言,这一时间复杂度在常数因子意义下已经最优。此后出现的算法,包括 Boyer–Myrvold 方法,提供了其他线性时间方案及其实用实现。有些实现还会在判定失败时,返回一个明确的细分子图,作为图不具有平面性的证据。

对于简单图,边数上界可以用于快速排除不符合条件的情况:若 n≥3n\geq3 且 m>3n−6m>3n-6,则该图不是平面图。通过这项检查并不能证明图具有平面性。完整的算法会维护一组约束,规定图的各个片段可以如何嵌入,以及它们与其他部分相连的顶点可以如何排列在面的边界上。深度优先搜索通常将图组织成一棵树,并将其余边视为连接顶点及其祖先的附加边。核心任务是判断这些附加连接能否以彼此相容的方式放置,而不造成必然的交叉。

按连通性进行分解可以简化这一问题。一个图是平面图,当且仅当它的每个块都是平面图;这里的块指极大二连通部分,桥则单独处理。在二连通图内部,沿分离顶点对进行分解,可以表示各个分量可能的排列方式。SPQR树是用于这一目的的标准数据结构:它记录串联、并联和刚性分量,并以紧凑的形式描述嵌入的各种选择。其中的刚性分量与三连通平面图嵌入的唯一性密切相关。

找到嵌入后,可以使用旋转系统或双向连接边表来支持对面和边的两侧进行操作。在半边表示中,每条边都有两条有向记录,每条记录都包含指向其反向记录以及沿面边界相邻记录的链接。对于一个已嵌入平面的连通图,这些结构可以在线性时间内枚举所有面的边界游走。随后,绘图算法便可为顶点指定几何坐标。

相关的优化问题通常比平面性判定更难。在一般图中寻找最大的平面子图,或使画法中的交叉数最少,都是计算上困难的问题。嵌入也不会自动满足美观或工程方面的目标,例如边较短、夹角较大、折弯较少,或顶点位于指定位置。这些都是额外的问题,各自有其约束和复杂度。

分隔集、算法与实际模型

平面性不仅限制了图的边密度,也限制了图中大块区域之间的连接方式。理查德·利普顿和罗伯特·塔扬于 1979 年证明的平面分隔集定理指出,任意一个有 nn 个顶点的平面图,都存在一个由 O(n)O(\sqrt n) 个顶点组成的集合,移除这些顶点后,剩余各连通分量的顶点数都不超过 2n/32n/3。该定理的加权形式所平衡的是顶点的非负权重,而不只是顶点数。在计算各连通分量的大小或权重之前,要先移除分隔集本身。

平方根这一量级基本上已是最优的。一个有 nn 个顶点、形状近似正方形的网格图,需要规模为 n\sqrt n 量级的分隔集,才能将其分成大小相近的几块。另一方面,分隔树所需的代价要小得多:只要选取一个合适的顶点并将其移除,就能使剩余各连通分量的顶点数都不超过原来的一半。因此,这一定理给出的是平面图在最坏情况下的保证,并不是说每个平面图都需要很大的分隔集。

递归构造分隔集可以支持分治算法。算法将图分成较小的区域,分别处理各个区域,同时沿着它们相对较小的边界协调信息。这种做法能带来多大收益,取决于具体问题需要多少边界信息。分隔集方法应用于最短路径算法、地理网络的数据结构以及优化问题的近似方案。

分隔集在数值线性代数中也很重要。对具有局部相互作用的二维区域进行离散化,往往会产生一个稀疏矩阵,其对应的图是平面图,或与平面网格密切相关。嵌套剖分法在进行矩阵分解之前,利用分隔集递归地对变量排序。与不合适的排序相比,这种排序可以大幅减少填充,也就是在高斯消元法过程中产生的新的非零元素。数值计算的结果仍取决于矩阵本身、矩阵的对称性、网格以及分解方法;仅凭平面性,并不能确定一个普遍适用的计算成本。

许多难题即使限制在平面图上,仍然很难求解。例如,在平面图上寻找最大独立顶点集仍然是 NP 难问题。不过,平面结构使得有用的近似求解成为可能。布伦达·贝克于 1994 年提出的方法,通过移除嵌入中选定的若干层,得到树宽有界的子图,再分别求解这些子图上的问题,并合并结果。对于若干优化问题,这种方法可以得到多项式时间近似方案:对于每个固定的精度要求,算法都能在多项式时间内运行,并在可控的误差范围内逼近最优解。

在实际应用中,判断一个网络是否确实为平面图,也需要谨慎。只有当道路实际相连时,道路交叉处才对应图中的顶点;立交桥可能使抽象的道路网络成为非平面图。单层电路布线模型类似于平面嵌入问题,而多层电路板允许连接线路在不同层上彼此跨越。因此,仅凭地理位置相近或采用二维可视化,并不能断定网络具有平面性。

外平面性、交叉与其他曲面上的嵌入

外平面图存在一种嵌入,使每个顶点都位于外部面的边界上。这一条件比平面性更强。例如,K4K_4 是平面图,却不是外平面图。一个图是外平面图,当且仅当它既不含 K4K_4 也不含 K2,3K_{2,3} 作为子式。具有 n≥2n\geq2 个顶点的简单外平面图至多有 2n−32n-3 条边。极大外平面图可以表示为多边形的三角剖分,并且具有特别易于处理的分解结构。

另一种推广方式是衡量一个图偏离平面图的程度。交叉数是将图以符合规定的方式画在平面上时,边的交叉次数的最小值。一个图是平面图,当且仅当它的交叉数为零。这个最小值不同于某张给定图画中的交叉次数;不必要的弯折或不当的位置安排都可能使后者增多。定义中通常排除退化的重合情形,例如多条边在同一个非顶点处相交,以确保交叉次数的计数方式一致。

除了允许交叉,也可以改用其他曲面。图的可定向亏格是使该图能够无交叉地嵌入某个可定向闭曲面所需的最少柄数。平面图的亏格为零,因为球面没有柄。K5K_5 和 K3,3K_{3,3} 都可以嵌入亏格为一的环面。从射影平面开始的不可定向曲面,则对应另一种概念,即不可定向亏格。

欧拉公式也可以推广到这些情形。对于以胞腔嵌入方式嵌入亏格为 gg 的可定向曲面的连通图,有

n−m+f=2−2g.n-m+f=2-2g.

胞腔嵌入是指每个面都同胚于开圆盘的嵌入。这一限定至关重要:仅仅把图画在曲面上,并不能保证对其补集中的区域进行计数就能得到该曲面的欧拉特征。对于具有 kk 个交叉帽的不可定向闭曲面,相应的值为 2−k2-k。

对于无限图,还需要作进一步区分。对有限图而言,组合意义下的平面嵌入与通常的无交叉画法可以直接对应。对无限图而言,顶点和边可能出现聚集,而聚点附近的行为会影响嵌入的含义。在通常的广义定义下,一个无限图是平面图,当且仅当它的所有有限子图都是平面图;但这并不自动保证它存在没有聚点的局部有限画法。因此,可能需要分别考察连通局部有限图、它的端以及其画法的紧化。这些问题将无限图论与空间拓扑联系起来,超出了有限平面嵌入图的范畴。