图的交叉数 图的交叉数是图论中研究图在平面上绘制时不可避免的交叉点数量的一个参数。它源于一个直观的问题：如何将一个给定的图“画”在平面上，使得边与边之间的交叉尽可能少？ 基本定义 首先，我们有一个抽象的图 G，由顶点集合 V 和边集合 E 组成。 当我们说“画”这个图时，指的是一个 画法 或 绘制 。具体来说，就是将每个顶点映射到平面上的一个点，将每条边映射为连接其两个端点的一条曲线。 在一个画法中，我们要求： 顶点的位置不能重合。 边不能穿过顶点（除了其自身的端点）。 如果两条边共享一个内部点（即非端点），我们称这两条边在该点发生了 交叉 。 一个画法的 交叉数 被定义为该画法中边与边之间交叉点的总数。注意，我们通常计算的是两个边交叉一次的点，并且假设在交叉点没有三条或以上的边同时穿过（这种情形可以通过微小的扰动避免）。 图 G 的 交叉数 ，记作 cr(G)，定义为所有可能画法中，交叉数的最小值。也就是说，cr(G) 是绘制图 G 时无法避免的最少交叉数目。 研究动机与背景 交叉数的研究起源于 平面图 的判定。如果一个图存在一种画法使得边与边之间完全没有交叉（即 cr(G) = 0），那么这个图就是一个 平面图 。因此，交叉数可以看作是衡量一个图“偏离”平面图程度的指标。cr(G) 越大，图在某种意义上“越不平面”。 一个重要的实际应用领域是 电路板设计 和 网络可视化 。在印刷电路板（PCB）上，我们希望导线（图的边）之间的交叉越少越好，因为交叉通常意味着需要在不同层之间穿孔连接，增加了成本和复杂性。同样，在绘制网络拓扑图、流程图等时，减少交叉可以提高图形的可读性。 交叉数问题本身也是一个有趣的组合优化问题：给定一个图，找出其交叉数，或者找出一个能达到或接近该交叉数的画法。 基本性质与已知结论 平面图判定 ：cr(G) = 0 当且仅当 G 是平面图。这直接联系到库拉托夫斯基定理和瓦格纳定理。 下界 ：寻找交叉数的下界是研究的核心之一。一个经典且重要的下界是 交叉引理 ，由 Ajtai, Chvátal, Newborn, Szemerédi 和 Leighton 独立发现。它指出：对于任意具有 n 个顶点和 m 条边的图 G，如果 m > 4n，则存在一个只依赖于 n 和 m 的常数 c，使得 cr(G) ≥ c * (m³ / n²)。这个引理揭示了边数远大于顶点数时，交叉数必然很大。 上界与具体图的交叉数 ：对于某些特定类型的图，其交叉数是已知的。 完全图 K_ n ：将 n 个顶点放置在凸多边形顶点上，并连接所有顶点对，这种画法的交叉数可以作为上界。但确定精确的 cr(K_ n) 是一个著名的未解决问题，目前只对较小的 n 有确切值。 完全二分图 K_ {a,b} ：同样，其精确交叉数也只在 a, b 较小时已知。一种常见的画法是將二分图的两部分顶点分别放在两条平行线上，此时交叉数易于计算，但这通常不是最优画法。 计算复杂性 ：确定任意一个图的交叉数是一个 NP-难问题。这意味着不存在一个高效（多项式时间）的算法能为所有图精确计算出交叉数，除非 P = NP。因此，研究多集中于寻找好的上界、下界以及针对特殊图类的算法。 相关概念与扩展 直线段绘制 ：如果要求画法中的每条边都是直线段，则对应的最小交叉数称为 直线段交叉数 。有些图在直线段绘制下的交叉数会大于允许边为曲线时的交叉数。 奇交叉数 与 对交叉数 ：这些是交叉数的变体。奇交叉数只计算与奇数条边交叉的边产生的交叉点。对交叉数则考虑将图画在曲面上，并计算成对交叉的最小数量。这些变体有时能提供不同的视角或更容易处理。 可画性 ：给定一个图和一个整数 k，判断是否存在一个交叉数不超过 k 的画法，这个判定问题是 NP-完全的。但当 k 固定时，存在一个时间复杂度为 O(n²) 的算法来判断 cr(G) ≤ k 是否成立（利用了图的可定义性理论）。 总结来说，图的交叉数是一个连接了图的可平面性、组合优化和计算复杂性的重要概念。它从一个非常直观的绘图问题出发，却引出了深刻的理论结果和具有挑战性的开放问题。