跳转到内容

交叉数

维基百科,自由的百科全书
希伍德图英语Heawood graph的一个画法,其有三个交叉。此为所有画法中,交叉个数的最小可能值,所以该图的交叉数为

图论交叉数是将画在平面上时,边的交叉点的最小数目。若,则称为平面图。在图形制图英语graph drawing方面,计算图的交叉数仍是一个重要问题,因为读者研究发现,画图的交叉越少,越有利于读者理解。[1]

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

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

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

给定一个图,计算其交叉数是一个NP难问题。[5]

定义

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

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

特殊情况

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

完全二部图

的一个最优画法,显示图兰砖厂问题中,若有4个仓(黄点)和7个窑(蓝点),则需要18个交叉(红点)。

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

卡齐米日·扎兰凯维奇英语Kazimierz Zarankiewicz尝试解决图兰砖厂问题,[9]但其证明有错。不过,他成功推导出完全二部图交叉数的一个上界

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

完全图与图染色

完全图的交叉数问题最先由安东尼·希尔英语Anthony Hill (artist)提出,并于1960年出版。[11]希尔及其合作者约翰·恩斯特英语John Ernest皆为对数学甚感兴趣的构成主义艺术家。两位不仅提出了问题,还猜想了该交叉数的公式,公式由理查·盖英语Richard K. Guy于1960年出版。[11]具体来说,已知总有一种画法,其交叉的数目为

上式在时,取值分别为,见整数数列线上大全A000241号数列。希尔等人猜想,不存在更好的画法,即上式给出了完全图的交叉数汤玛士·沙提英语Thomas L. Saaty于1964年独立地作出了同一个猜想。[12]

对于,沙提验证了上式确实给出交叉的最小可能数目。潘(Shengjun Pan)和布鲁斯·里希特(Bruce Richter)验证了的情况。[13]

2007年,米高·艾伯森(Michael O. Albertson)提出了艾伯森猜想英语Albertson conjecture,其断言:在所有色数的图之中,完全图的交叉数最小。换言之,若此猜想与上段的猜想均成立,则每个染色数为的图,交叉数皆不小于上段的公式。现已证明,艾伯森猜想对于成立。[14]

立方图

已知交叉数为的最小的立方图,其顶点数分别为OEIS数列A110507),如下表所记:

交叉数 最小立方图例子 顶点数
1 完全二部图 6
2 佩特森图 10
3 希伍德图英语Heawood graph 14
4 莫比乌斯-坎特图英语Möbius-Kantor graph 16
5 帕普斯图英语Pappus graph 18
6 笛沙格图英语Desargues graph 20
7 有4个不同构的例子,但并无熟知命名[15] 22
8 瑙鲁图英语Nauru graph麦基图英语McGee graph、(3,7)-笼图英语cage graph[16] 24
9 麦基图加某一条边[17] 26
10 麦基图加某两条边[17] 28
11 考克斯特图[18] 28

2009年,爱德华·柏奇英语Ed Pegg和Geoffrey Exoo猜想交叉数为13的最小立方图为塔特-考克斯特图英语Tutte–Coxeter graph,以及交叉数为170的最小立方图为塔特12-笼英语Tutte 12-cage[16][19]

复杂度与近似

一般情况下,很难计算图的交叉数。米高·加里英语Michael Garey大卫·詹森英语David S. Johnson于1983年证明了计算交叉数是NP难问题。[5]即使仅考虑立方图[20],或者仅考虑将近平面的特殊情况(即可藉删走一条边使之变成平面图)[21],问题仍然NP难。另一个相关问题是计算仅能使用直线段画图时,交叉数目的最小值。该最小值称为直线交叉数(rectilinear crossing number)。该问题对于实数的存在理论英语existential theory of the reals完全的。[22]

另一方面,对于固定的常数,有高效算法判定交叉数是否小于。换言之,交叉数问题是固定参数可驯顺英语fixed-parameter tractable的。[23][24]但若不是常数,而是与输入大小有关的函数,例如,则问题仍然很难。对于度数有界的图,有高效的近似算法能够近似计算交叉数[25]实务上,常使用启发式算法,例如从空图开始,逐条边加入,使得每次产生的交叉数尽可能小。直线交叉数分布式计算计划(Rectilinear Crossing Number project)使用了此类算法。[26]

交叉数不等式

无向简单图恰有个顶点和条边,且,则交叉数满足不等式

此种边数、顶点数与交叉数的关系,最早由奥伊陶伊·米克洛什英语Miklós Ajtai瓦茨拉夫·赫瓦塔尔英语Václav Chvátal蒙提·纽邦英语Monty Newborn塞迈雷迪·安德烈四人[27]汤姆森·雷顿英语F. Thomson Leighton[28]分别独立发现,称为交叉数不等式或交叉数引理。不等式的上述版本是为伊尔·艾克曼(Eyal Ackerman)的结果,其中常数为截至2019年所知最优。[29]条件中的常数也可以缩少至更佳的,但代价是要换成较差的[27][28]

雷顿之所以研究交叉数,是为了理论计算机科学中,超大型集成电路设计方面的应用。[28]其后,Székely 发现交叉数不等式用在关联几何方面,能够简短证明一些重要定理,例如塞迈雷迪-特罗特定理贝克定理英语Beck's theorem (geometry)[30]塔马尔·戴伊英语Tamal Dey类似地证明了几何k-集英语K-set (geometry)数的上界。[31]

变式

若仅允许用直线段画边,而非任意曲线,则一些图需要更多交叉才能画出。对于此类画法,交叉数目的最小可能值称为直线交叉数。直线交叉数必不小于交叉数,甚至对某些图而言,直线交叉数严格大于交叉数。完全图的直线交叉数依序为OEIS数列A014540)。已知直至的直线交叉数,而则可能需要7233或7234个交叉。直线交叉数分布式计算计划(Rectilinear Crossing Number project)收集了更多数据。[26]

若一个图有画法使得每条边至多个交叉,但不能更少,则称为其局部交叉数(local crossing number)。若图有画法使每条边至多个交叉,则称其为-平面图-planar)。[32]

其他变式包括两两相交数(pairwise crossing number,即任何画法中,有交叉的边对数目的最小可能值)和奇相交数(odd crossing number,即任何画法中,交叉次数恰为奇数的边对数目的最小可能值)。奇相交数不大于两两相交数,两两相交数也不大于相交数。然而,哈纳尼-塔特定理英语Hanani–Tutte theorem说明,若这三个数中有任何一个为零,则皆为零。[6] Schaefer (2014, 2018综述了许多变式。[33][34]

参考

  1. ^ Purchase, Helen C.; Cohen, Robert F.; James, Murray I. Brandenburg, Franz-Josef , 编. Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings. Lecture Notes in Computer Science 1027. Springer: 435–446. 1995. doi:10.1007/BFb0021827可免费查阅.  |contribution=被忽略 (帮助).
  2. ^ Turán, P. A Note of Welcome. Journal of Graph Theory. 1977, 1: 7–9. doi:10.1002/jgt.3190010105. 
  3. ^ Bronfenbrenner, Urie. The graphic presentation of sociometric data. Sociometry. 1944, 7 (3): 283–289. JSTOR 2785096. doi:10.2307/2785096. The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines. 
  4. ^ Scheinerman, Edward R.; Wilf, Herbert S. The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability. American Mathematical Monthly. 1994, 101 (10): 939–943. JSTOR 2975158. doi:10.2307/2975158. 
  5. ^ 5.0 5.1 Garey, M. R.; Johnson, D. S. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods. 1983, 4 (3): 312–316. MR 0711340. doi:10.1137/0604033. 
  6. ^ 6.0 6.1 6.2 Pach, J.; Tóth, G. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998): 617–626. 1998. doi:10.1109/SFCS.1998.743512.  |contribution=被忽略 (帮助).
  7. ^ de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, B.; Salazar, G. Improved bounds for the crossing numbers of Km,n and Kn. SIAM Journal on Discrete Mathematics. 2006, 20 (1): 189–202 [2021-06-23]. S2CID 1509054. arXiv:math/0404142可免费查阅. doi:10.1137/S0895480104442741. (原始内容存档于2021-06-28). 
  8. ^ Pach, János; Sharir, Micha. 5.1 Crossings—the Brick Factory Problem. Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. Mathematical Surveys and Monographs 152. American Mathematical Society. 2009: 126–127. 
  9. ^ Zarankiewicz, K. On a Problem of P. Turán Concerning Graphs. Fundamenta Mathematicae. 1954, 41: 137–145. doi:10.4064/fm-41-1-137-145可免费查阅. 
  10. ^ Guy, Richard K. The decline and fall of Zarankiewicz's theorem. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). Academic Press, New York. 1969: 63–69. MR 0253931. .
  11. ^ 11.0 11.1 Guy, R. K. A combinatorial problem. Nabla (Bulletin of the Malayan Mathematical Society). 1960, 7: 68–72. 
  12. ^ Saaty, T.L. The minimum number of intersections in complete graphs. Proceedings of the National Academy of Sciences of the United States of America. 1964, 52 (3): 688–690. Bibcode:1964PNAS...52..688S. PMC 300329可免费查阅. PMID 16591215. doi:10.1073/pnas.52.3.688. 
  13. ^ Pan, Shengjun; Richter, R. Bruce. The crossing number of K11 is 100. Journal of Graph Theory. 2007, 56 (2): 128–134. MR 2350621. doi:10.1002/jgt.20249. .
  14. ^ Barát, János; Tóth, Géza. Towards the Albertson Conjecture. 2009. arXiv:0909.0413可免费查阅 [math.CO]. 
  15. ^ Weisstein, Eric W. (编). Graph Crossing Number. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 
  16. ^ 16.0 16.1 Pegg, E. T.; Exoo, G. Crossing Number Graphs. Mathematica Journal. 2009, 11 (2). doi:10.3888/tmj.11.2-2. 
  17. ^ 17.0 17.1 Sloane, N.J.A. (编). Sequence A110507 (Number of nodes in the smallest cubic graph with crossing number n.). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. 
  18. ^ Haythorpe, Michael; Newcombe, Alex, There are no Cubic Graphs on 26 Vertices with Crossing Number 11, 2018, arXiv:1804.10336可免费查阅 
  19. ^ Exoo, G. Rectilinear Drawings of Famous Graphs. [2021-06-24]. (原始内容存档于2021-06-24). 
  20. ^ Hliněný, P. Crossing number is hard for cubic graphs. Journal of Combinatorial Theory. Series B. 2006, 96 (4): 455–471. MR 2232384. doi:10.1016/j.jctb.2005.09.009. 
  21. ^ Cabello S. and Mohar B. Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard. SIAM Journal on Computing. 2013, 42 (5): 1803–1829. S2CID 6535755. arXiv:1203.5944可免费查阅. doi:10.1137/120872310. 
  22. ^ Schaefer, Marcus. Complexity of some geometric and topological problems (PDF). Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers. Lecture Notes in Computer Science 5849. Springer-Verlag: 334–344. 2010 [2020-11-04]. ISBN 978-3-642-11804-3. doi:10.1007/978-3-642-11805-0_32可免费查阅. (原始内容存档 (PDF)于2021-06-26). .
  23. ^ Grohe, M. Computing crossing numbers in quadratic time. Journal of Computer and System Sciences. 2005, 68 (2): 285–302. MR 2059096. arXiv:cs/0009010可免费查阅. doi:10.1016/j.jcss.2003.07.008. 
  24. ^ Kawarabayashi, Ken-ichi; Reed, Bruce. Computing crossing number in linear time. Proceedings of the 29th Annual ACM Symposium on Theory of Computing: 382–390. 2007. ISBN 978-1-59593-631-8. doi:10.1145/1250790.1250848. 
  25. ^ Even, Guy; Guha, Sudipto; Schieber, Baruch. Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas. SIAM Journal on Computing. 2003, 32 (1): 231–252. doi:10.1137/S0097539700373520. 
  26. ^ 26.0 26.1 Oswin Aichholzer. Rectilinear Crossing Number project. (原始内容存档于2012-12-30). , and Rectilinear Crossing Number页面存档备份,存于互联网档案馆) on the Institute for Software Technology at Graz, University of Technology (2009).
  27. ^ 27.0 27.1 Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. Crossing-free subgraphs. Theory and Practice of Combinatorics. North-Holland Mathematics Studies 60: 9–12. 1982. MR 0806962. 
  28. ^ 28.0 28.1 28.2 Leighton, T. Complexity Issues in VLSI. Foundations of Computing Series. Cambridge, MA: MIT Press. 1983. 
  29. ^ Ackerman, Eyal. On topological graphs with at most four crossings per edge (PDF). 2013. (原始内容 (PDF)存档于2014-07-14). 
  30. ^ Székely, L. A. Crossing numbers and hard Erdős problems in discrete geometry. Combinatorics, Probability and Computing. 1997, 6 (3): 353–358. MR 1464571. doi:10.1017/S0963548397002976. 
  31. ^ Dey, T. K. Improved bounds for planar k-sets and related problems. Discrete and Computational Geometry. 1998, 19 (3): 373–382. MR 1608878. doi:10.1007/PL00009354可免费查阅. 
  32. ^ Ringel, Gerhard. Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 1965, 29 (1–2): 107–117. MR 0187232. S2CID 123286264. doi:10.1007/BF02996313 (德语). 
  33. ^ Schaefer, Marcus. The graph crossing number and its variants: a survey. The Electronic Journal of Combinatorics. 2014. DS21 [2021-06-25]. (原始内容存档于2021-06-29). 
  34. ^ Schaefer, Marcus. Crossing Numbers of Graphs. CRC Press. 2018.