交叉数

在图论，交叉数$\text{cr}(G)$是将图$G$画在平面上时，边的交叉点的最小数目。若$\hbox{cr}(G)=0$，则$G$称为平面图。在图形制图方面，计算图的交叉数仍是一个重要问题，因为读者研究发现，画图的交叉越少，越有利于读者理解。

交叉数的研究始于图兰砖厂问题。图兰·帕尔想求砖厂中，将每个窑炉各与全部货仓用路轨连接的最优方案，使路轨的交叉尽可能少。按上述定义，即是问完全二部图的交叉数。同一问题约莫同时在社会学研究提出，因为事关社会关系图的绘制。图兰猜想了完全二部图交叉数的公式，但该公式迄今未获证，完全图的交叉数公式亦然。

交叉数不等式断言，若边数$e$与顶点数$n$的比值大于某个常数，则交叉数不小于$e^3/n^2$乘以另一个固定的常数。此结论在超大规模集成电路设计与组合几何方面有应用。

如无特别注明，交叉数允许使用任意曲线来画边。另一个相关概念是直线交叉数，其要求仅使用直线段来画边，所以未必等于交叉数。更具体说，完全图$K_n$的直线交叉数就是平面上处于一般位置的$n$个点所能组成的凸四边形的最少数目，因为每个凸四边形的两条对角线产生一个交叉。直线交叉数问题与幸福结局问题密切相关。

给定一个图，计算其交叉数是一个NP难问题。

## 定义

定义交叉数之前，先定义无向图的画法。图的画法是一个映射，其将图的顶点映到平面上互异的点，并将每条边映到一条连接其两端的曲线段，但顶点不能映到其他边上（除非该边以其为顶点），且若两条边的曲线段在公共顶点以外相交，则其仅产生有限多个交叉，并于每个交叉处横截相交。若一个交叉点有多于两条边相交，则每对相交边计算一次。图的交叉数是所有画法当中，交叉的数目的最小值。

一些作者对于画法有更多限制，例如要求每对边的交集至多只有一点（可为公共端点或交叉）。对于上段定义的交叉数，此项限制没有任何影响，因为交叉最少的画法当中，两条边必定相交至多一次。（若两条边有公共端点，而且相交，则可以将首个交点以前的两段曲线互换，从而减少一个交叉。类似地，若两条边有两个或更多交叉，则可以将相邻两个交叉之间的两段曲线互换，以减少两个交叉。）然而，若考虑交叉数的变式定义，例如只计算有多少对边交叉（称为两两交叉数），而非有多少个交叉，则上述限制确实会影响两两交叉数的值。

## 特殊情况

截止2015年4月，仅得很少几类图的交叉数为人所知。即使是完全图、完全二部图、两个环的积等结构较简单的图，也仅得初始几个的交叉数是已知的，但交叉数的下界方面，已有一定进展。

### 完全二部图

<image>

在第二次世界大战期间，匈牙利数学家图兰·帕尔被迫在砖厂工作，要将一车车的砖从窑炉推到货仓。工厂的每个窑炉到每个货仓之间各有一条路轨，而砖车在路轨交叉处特别难推。于是，图兰提出其砖厂问题：窑炉、货仓和路轨应如何安排，才能使交叉的数目最少？数学上，窑炉和货仓可视为完全二部图的顶点，而路轨则是二部图的边。于是工厂的布局就是该图在平面上的一个画法，换言之问题变成：

完全二部图的画法中，交叉的最少数目是多少？

卡齐米日·扎兰凯维奇尝试解决图兰砖厂问题，但其证明有错。不过，他成功推导出完全二部图$K_{m,n}$交叉数的一个上界：

$$\textrm{cr}(K_{m,n}) \le \left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{m}{2}\right\rfloor\left\lfloor\frac{m-1}{2}\right\rfloor.$$

一个猜想是，上述上界确实是所有完全二部图的交叉数。

### 完全图与图染色

完全图的交叉数问题最先由安东尼·希尔提出，并于1960年出版。希尔及其合作者约翰·恩斯特皆为对数学甚感兴趣的构成主义艺术家。两位不仅提出了问题，还猜想了该交叉数的公式，公式由理查·盖于1960年出版。具体来说，已知$K_p$总有一种画法，其交叉的数目为

$$\frac{1}{4} \left\lfloor\frac{p}{2}\right\rfloor\left\lfloor\frac{p-1}{2}\right\rfloor\left\lfloor\frac{p-2}{2}\right\rfloor\left\lfloor\frac{p-3}{2}\right\rfloor.$$

上式在$p = 5, 6, \cdots, 12$时，取值分别为$1, 3, 9, 18, 36, 60, 100, 150$，见整数数列线上大全的A000241号数列。希尔等人猜想，不存在更好的画法，即上式给出了完全图的交叉数$\text{cr}(K_p)$。汤玛士·沙提于1964年独立地作出了同一个猜想。

对于$p \le 10$，沙提验证了上式确实给出交叉的最小可能数目。潘（Shengjun Pan)和布鲁斯·里希特（Bruce Richter）验证了$p = 11, 12$的情况。

2007年，米高·艾伯森（Michael O. Albertson）提出了艾伯森猜想，其断言：在所有色数为$p$的图之中，完全图$K_p$的交叉数最小。换言之，若此猜想与上段的猜想均成立，则每个染色数为$p$的图，交叉数皆不小于上段的公式。现已证明，艾伯森猜想对于$p \le 16$成立。

### 立方图

已知交叉数为$1$至$11$的最小的立方图，其顶点数分别为$6, 10, 14, 16, 18, 20, 22, 24, 26, 28, 28$，如下表所记：

交叉数｜最小立方图例子｜顶点数

1｜完全二部图$K_{3,3}$｜6

2｜佩特森图｜10

3｜希伍德图｜14

4｜莫比乌斯－坎特图｜16

5｜帕普斯图｜18

6｜笛沙格图｜20

7｜有4个不同构的例子，但并无熟知命名｜22

8｜瑙鲁图、麦基图、(3,7)-笼图｜24

9｜麦基图加某一条边｜26

10｜麦基图加某两条边｜28

11｜考克斯特图｜28

2009年，爱德华·柏奇和Geoffrey Exoo猜想交叉数为13的最小立方图为塔特－考克斯特图，以及交叉数为170的最小立方图为塔特12-笼。

## 复杂度与近似

一般情况下，很难计算图的交叉数。米高·加里和大卫·詹森于1983年证明了计算交叉数是NP难问题。即使仅考虑立方图，或者仅考虑将近平面的特殊情况（即可藉删走一条边使之变成平面图），问题仍然NP难。另一个相关问题是计算仅能使用直线段画图时，交叉数目的最小值。该最小值称为直线交叉数（rectilinear crossing number）。该问题对于实数的存在理论是完全的。

另一方面，对于固定的常数$k$，有高效算法判定交叉数是否小于$k$。换言之，交叉数问题是固定参数可驯顺的。但若$k$不是常数，而是与输入大小有关的函数，例如$k=|V|/2$，则问题仍然很难。对于度数有界的图$G$，有高效的近似算法能够近似计算交叉数$\text{cr}(G)$。实务上，常使用启发式算法，例如从空图开始，逐条边加入，使得每次产生的交叉数尽可能小。直线交叉数分布式计算计划（Rectilinear Crossing Number project）使用了此类算法。

## 交叉数不等式

若无向简单图$G$恰有$n$个顶点和$e$条边，且$e>7n$，则交叉数$\text{cr}(G)$满足不等式

$$\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.$$

此种边数、顶点数与交叉数的关系，最早由奥伊陶伊·米克洛什、瓦茨拉夫·赫瓦塔尔、蒙提·纽邦、塞迈雷迪·安德烈四人和汤姆森·雷顿分别独立发现，称为交叉数不等式或交叉数引理。不等式的上述版本是为伊尔·艾克曼（Eyal Ackerman）的结果，其中常数$29$为截至2019年所知最优。条件中的常数$7$也可以缩少至更佳的$4$，但代价是$29$要换成较差的$64$。

雷顿之所以研究交叉数，是为了理论计算机科学中，超大型积体电路设计方面的应用。其后，Székely 发现交叉数不等式用在关联几何方面，能够简短证明一些重要定理，例如塞迈雷迪－特罗特定理和贝克定理。塔马尔·戴伊类似地证明了几何k-集数的上界。

## 变式

若仅允许用直线段画边，而非任意曲线，则一些图需要更多交叉才能画出。对于此类画法，交叉数目的最小可能值称为直线交叉数。直线交叉数必不小于交叉数，甚至对某些图而言，直线交叉数严格大于交叉数。完全图$K_5$至$K_{12}$的直线交叉数依序为$1, 3, 9, 19, 36, 62, 102, 153$A014540。已知直至$K_{27}$的直线交叉数，而$K_{28}$则可能需要7233或7234个交叉。直线交叉数分布式计算计划（Rectilinear Crossing Number project）收集了更多数据。

若一个图有画法使得每条边至多$k$个交叉，但$k$不能更少，则称$k$为其局部交叉数（local crossing number）。若图有画法使每条边至多$k$个交叉，则称其为$k$-平面图（$k$-planar）。

其他变式包括两两相交数（pairwise crossing number，即任何画法中，有交叉的边对数目的最小可能值）和奇相交数（odd crossing number，即任何画法中，交叉次数恰为奇数的边对数目的最小可能值）。奇相交数不大于两两相交数，两两相交数也不大于相交数。然而，哈纳尼-塔特定理说明，若这三个数中有任何一个为零，则皆为零。综述了许多变式。