在图论，交叉数是将图画在平面上时，边的交叉点的最小数目。若，则称为平面图。在图形制图方面，计算图的交叉数仍是一个重要问题，因为读者研究发现，画图的交叉越少，越有利于读者理解。[1]
交叉数的研究始于图兰砖厂问题。图兰·帕尔想求砖厂中，将每个窑炉各与全部货仓用路轨连接的最优方案，使路轨的交叉尽可能少。按上述定义，即是问完全二部图的交叉数。[2]同一问题约莫同时在社会学研究提出，因为事关社会关系图的绘制。[3] 图兰猜想了完全二部图交叉数的公式，但该公式迄今未获证，完全图的交叉数公式亦然。
交叉数不等式断言，若边数与顶点数的比值大于某个常数，则交叉数不小于乘以另一个固定的常数。此结论在超大规模集成电路设计与组合几何方面有应用。
如无特别注明，交叉数允许使用任意曲线来画边。另一个相关概念是直线交叉数，其要求仅使用直线段来画边，所以未必等于交叉数。更具体说，完全图的直线交叉数就是平面上处于一般位置的个点所能组成的凸四边形的最少数目，因为每个凸四边形的两条对角线产生一个交叉。直线交叉数问题与幸福结局问题密切相关。[4]
定义
定义交叉数之前，先定义无向图的画法。图的画法是一个映射，其将图的顶点映到平面上互异的点，并将每条边映到一条连接其两端的曲线段，但顶点不能映到其他边上（除非该边以其为顶点），且若两条边的曲线段在公共顶点以外相交，则其仅产生有限多个交叉，并于每个交叉处横截相交。若一个交叉点有多于两条边相交，则每对相交边计算一次。图的交叉数是所有画法当中，交叉的数目的最小值。[6]
一些作者对于画法有更多限制，例如要求每对边的交集至多只有一点（可为公共端点或交叉）。对于上段定义的交叉数，此项限制没有任何影响，因为交叉最少的画法当中，两条边必定相交至多一次。（若两条边有公共端点，而且相交，则可以将首个交点以前的两段曲线互换，从而减少一个交叉。类似地，若两条边有两个或更多交叉，则可以将相邻两个交叉之间的两段曲线互换，以减少两个交叉。）然而，若考虑交叉数的变式定义，例如只计算有多少对边交叉（称为两两交叉数），而非有多少个交叉，则上述限制确实会影响两两交叉数的值。[6]
特殊情况
截止2015年4月，仅得很少几类图的交叉数为人所知。即使是完全图、完全二部图、两个环的积等结构较简单的图，也仅得初始几个的交叉数是已知的，但交叉数的下界方面，已有一定进展。[7]
在第二次世界大战期间，匈牙利数学家图兰·帕尔被迫在砖厂工作，要将一车车的砖从窑炉推到货仓。工厂的每个窑炉到每个货仓之间各有一条路轨，而砖车在路轨交叉处特别难推。于是，图兰提出其砖厂问题：窑炉、货仓和路轨应如何安排，才能使交叉的数目最少？数学上，窑炉和货仓可视为完全二部图的顶点，而路轨则是二部图的边。于是工厂的布局就是该图在平面上的一个画法，换言之问题变成： 完全二部图的画法中，交叉的最少数目是多少？[8]
卡齐米日·扎兰凯维奇尝试解决图兰砖厂问题，[9]但其证明有错。不过，他成功推导出完全二部图交叉数的一个上界：
一个猜想是，上述上界确实是所有完全二部图的交叉数。[10]
完全图的交叉数问题最先由安东尼·希尔提出，并于1960年出版。[11]希尔及其合作者约翰·恩斯特皆为对数学甚感兴趣的构成主义艺术家。两位不仅提出了问题，还猜想了该交叉数的公式，公式由理查·盖于1960年出版。[11]具体来说，已知总有一种画法，其交叉的数目为
上式在时，取值分别为，见整数数列线上大全的A000241号数列。希尔等人猜想，不存在更好的画法，即上式给出了完全图的交叉数。汤玛士·沙提于1964年独立地作出了同一个猜想。[12]
对于，沙提验证了上式确实给出交叉的最小可能数目。潘（Shengjun Pan)和布鲁斯·里希特（Bruce Richter）验证了的情况。[13]
2007年，米高·艾伯森（Michael O. Albertson）提出了艾伯森猜想，其断言：在所有色数为的图之中，完全图的交叉数最小。换言之，若此猜想与上段的猜想均成立，则每个染色数为的图，交叉数皆不小于上段的公式。现已证明，艾伯森猜想对于成立。[14]
已知交叉数为至的最小的立方图，其顶点数分别为（OEIS数列A110507），如下表所记：
...2009年，爱德华·柏奇和Geoffrey Exoo猜想交叉数为13的最小立方图为塔特－考克斯特图，以及交叉数为170的最小立方图为塔特12-笼。[16][19]
复杂度与近似
一般情况下，很难计算图的交叉数。米高·加里和大卫·詹森于1983年证明了计算交叉数是NP难问题。[5]即使仅考虑立方图[20]，或者仅考虑将近平面的特殊情况（即可藉删走一条边使之变成平面图）[21]，问题仍然NP难。另一个相关问题是计算仅能使用直线段画图时，交叉数目的最小值。该最小值称为直线交叉数（rectilinear crossing number）。该问题对于实数的存在理论是完全的。[22]
另一方面，对于固定的常数，有高效算法判定交叉数是否小于。换言之，交叉数问题是固定参数可驯顺的。[23][24]但若不是常数，而是与输入大小有关的函数，例如，则问题仍然很难。对于度数有界的图，有高效的近似算法能够近似计算交叉数。[25]实务上，常使用启发式算法，例如从空图开始，逐条边加入，使得每次产生的交叉数尽可能小。直线交叉数分布式计算计划（Rectilinear Crossing Number project）使用了此类算法。[26]
交叉数不等式
此种边数、顶点数与交叉数的关系，最早由奥伊陶伊·米克洛什、瓦茨拉夫·赫瓦塔尔、蒙提·纽邦、塞迈雷迪·安德烈四人[27]和汤姆森·雷顿[28]分别独立发现，称为交叉数不等式或交叉数引理。不等式的上述版本是为伊尔·艾克曼（Eyal Ackerman）的结果，其中常数为截至2019年所知最优。[29]条件中的常数也可以缩少至更佳的，但代价是要换成较差的。[27][28]
雷顿之所以研究交叉数，是为了理论计算机科学中，超大型集成电路设计方面的应用。[28]其后，Székely 发现交叉数不等式用在关联几何方面，能够简短证明一些重要定理，例如塞迈雷迪－特罗特定理和贝克定理。[30]塔马尔·戴伊类似地证明了几何k-集数的上界。[31]
变式
若仅允许用直线段画边，而非任意曲线，则一些图需要更多交叉才能画出。对于此类画法，交叉数目的最小可能值称为直线交叉数。直线交叉数必不小于交叉数，甚至对某些图而言，直线交叉数严格大于交叉数。完全图至的直线交叉数依序为（OEIS数列A014540）。已知直至的直线交叉数，而则可能需要7233或7234个交叉。直线交叉数分布式计算计划（Rectilinear Crossing Number project）收集了更多数据。[26]
若一个图有画法使得每条边至多个交叉，但不能更少，则称为其局部交叉数（local crossing number）。若图有画法使每条边至多个交叉，则称其为-平面图（-planar）。[32]
其他变式包括两两相交数（pairwise crossing number，即任何画法中，有交叉的边对数目的最小可能值）和奇相交数（odd crossing number，即任何画法中，交叉次数恰为奇数的边对数目的最小可能值）。奇相交数不大于两两相交数，两两相交数也不大于相交数。然而，哈纳尼-塔特定理说明，若这三个数中有任何一个为零，则皆为零。[6] Schaefer （2014, 2018）综述了许多变式。[33][34]
参考
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
