交叉數

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

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

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

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

交叉數不等式

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

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

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

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

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

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

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

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

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

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

參考

• http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/