查看“交叉數”的源代码

在[[圖論]]，'''交叉數'''是指一個[[圖]]在[[平面 (数学)|平面]]上，邊的交叉點的最小數目。

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

以<math>\hbox{cr}(G)</math>表示圖<math>G</math>的交叉數。若<math>\hbox{cr}(G)=0</math>，<math>G</math>稱為[[平面图 (图论)|平面圖]]。

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

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

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

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

: <math>\hbox{cr}(G) \ge e - 3v + 6</math>

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

: <math>p^4 \hbox{cr}(G) \ge p^2 e - 3 p v + 6</math>
: <math>\hbox{cr}(G) \ge p^{-2} e - 3 p^{-3} v + 6 p^{-4}</math>

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

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

: <math>\hbox{cr}(G) \ge e^3 / 64 v^2</math>

==參考==
* http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/

[[Category:圖論]]