交叉數

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

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

給定一個圖,計算其交叉數是一個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

參考[编辑]