交叉数
圖的畫法中,邊交叉的最少次數 / 维基百科,自由的 encyclopedia
在图论,交叉数是将图画在平面上时,边的交叉点的最小数目。若,则称为平面图。在图形制图(英语:graph drawing)方面,计算图的交叉数仍是一个重要问题,因为读者研究发现,画图的交叉越少,越有利于读者理解。[1]
交叉数的研究始于图兰砖厂问题(英语:Turán's brick factory problem)。图兰·帕尔想求砖厂中,将每个窑炉各与全部货仓用路轨连接的最优方案,使路轨的交叉尽可能少。按上述定义,即是问完全二部图的交叉数。[2]同一问题约莫同时在社会学研究提出,因为事关社会关系图(英语:sociogram)的绘制。[3] 图兰猜想了完全二部图交叉数的公式,但该公式迄今未获证,完全图的交叉数公式亦然。
交叉数不等式断言,若边数与顶点数的比值大于某个常数,则交叉数不小于乘以另一个固定的常数。此结论在超大规模集成电路设计与组合几何方面有应用。
如无特别注明,交叉数允许使用任意曲线来画边。另一个相关概念是直线交叉数,其要求仅使用直线段来画边,所以未必等于交叉数。更具体说,完全图的直线交叉数就是平面上处于一般位置的个点所能组成的凸四边形的最少数目,因为每个凸四边形的两条对角线产生一个交叉。直线交叉数问题与幸福结局问题密切相关。[4]