交叉数

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

希伍德图的一个画法，其有三个交叉。此为所有画法中，交叉个数的最小可能值，所以该图的交叉数为 ${\text{cr}}(G)=3$。

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

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

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

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

定义

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

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

特殊情况

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

完全二部图

$K_{4,7}$的一个最优画法，显示图兰砖厂问题中，若有4个仓（黄点）和7个窑（蓝点），则需要18个交叉（红点）。

主条目：图兰砖厂问题

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

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

${\textrm {cr}}(K_{m,n})\leq \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\leq 10$，沙提验证了上式确实给出交叉的最小可能数目。潘（Shengjun Pan)和布鲁斯·里希特（Bruce Richter）验证了$p=11,12$的情况。

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

立方图

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

交叉数	最小立方图例子	顶点数
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}}{29n^{2}}}.$

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

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

变式

若仅允许用直线段画边，而非任意曲线，则一些图需要更多交叉才能画出。对于此类画法，交叉数目的最小可能值称为直线交叉数。直线交叉数必不小于交叉数，甚至对某些图而言，直线交叉数严格大于交叉数。完全图$K_{5}$至$K_{12}$的直线交叉数依序为$1,3,9,19,36,62,102,153$（OEIS数列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，即任何画法中，交叉次数恰为奇数的边对数目的最小可能值）。奇相交数不大于两两相交数，两两相交数也不大于相交数。然而，哈纳尼-塔特定理说明，若这三个数中有任何一个为零，则皆为零。 Schaefer （2014, 2018）综述了许多变式。

参考

• http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/ （页面存档备份，存于互联网档案馆）