交叉數

在圖論，交叉數是指一個圖在平面上，邊的交叉點的最小數目。

一個圖在平面上可以有多種畫法，若有多於兩條邊相交於同一點，每對相交邊計算一次。

以${\hbox{cr}}(G)$表示圖$G$的交叉數。若${\hbox{cr}}(G)=0$，$G$稱為平面圖。

給定一個圖，計算其交叉數是一個NP-hard的問題（1983年）。

如女口Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves. A variation of this concept, the rectilinear crossing number, requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of n points in general position. The problem of determining this number is closely related to the happy ending problem.

特殊情況

截止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}$	4
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，有高效的近似算法能夠近似計算交叉數cr(G)。實務上，常使用啟發式算法，例如從空圖開始，逐條邊加入，使得每次產生的交叉數儘可能小。直線交叉數分布式计算計劃（Rectilinear Crossing Number project）使用了此類算法。

交叉數不等式

主条目：交叉數不等式

交叉數不等式說明了給定邊數目$e$和頂點數目$v$，${\hbox{cr}}(G)$的下界。

已知平面圖都符合$v-e+f=2$（歐拉公式）。考慮邊面的對應數目，每條邊剛好屬於某兩個面，而每個面最小有三條邊，因此對於平面圖有$3f\leq 2e$。為了消去$f$，代入$f=2+e-v$，得$e\leq 3v-6$。

再考慮一般圖$G$，如何將它「變成」平面圖。如果我們在每個相交點，都去掉一條邊，則剩下的圖必是平面圖。這個新的平面圖的邊數目為$e-{\hbox{cr}}(G)$，而頂點數目v不變。因此，對於所有的圖都有

${\hbox{cr}}(G)\geq e-3v+6$

接下來使用機率方法，從G中構作一個新的圖。考慮在G所有頂點中選取某些點作為新圖G'的頂點；若G中的某一條邊的兩個端點都在V(G')內，則E(G')亦有該條邊；因此，G中的一個交點仍然存在在G'中的條件，是該交點涉及的2條邊的4個不同端點都保留在G'中。現在隨機選取G中的pv個頂點（$0<p\leq 1$），則 $|V(G')|=pv,|E(G')|=p^{2}e,|V(G')|=p^{4}{\hbox{cr}}(G)$，代入上面的不等式：

$p^{4}{\hbox{cr}}(G)\geq p^{2}e-3pv+6$

${\hbox{cr}}(G)\geq p^{-2}e-3p^{-3}v+6p^{-4}$

求${\hbox{cr}}(G)$的下界，希望能使上面的不等式右方儘可能大。

當$e$相當大時，考慮$e\geq 4v$，可以取$p=4v/e$，整理後得：

${\hbox{cr}}(G)\geq e^{3}/64v^{2}$

參考

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