交叉數

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

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

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

表示圖的交叉數。若稱為平面圖

給定一個圖,計算其交叉數是一個NP-hard的問題(1983年)。

交叉數不等式[编辑]

交叉數不等式說明了給定邊數目和頂點數目的下界。

已知平面圖都符合歐拉公式)。考慮邊面的對應數目,每條邊剛好屬於某兩個面,而每個面最小有三條邊,因此對於平面圖有。為了消去,代入,得

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

接下來使用機率方法,從G中構作一個新的圖。考慮在G所有頂點中選取某些點作為新圖G'的頂點;若G中的某一條邊的兩個端點都在V(G')內,則E(G')亦有該條邊;因此,G中的一個交點仍然存在在G'中的條件,是該交點涉及的2條邊的4個不同端點都保留在G'中。現在隨機選取G中的pv個頂點(),則 ,代入上面的不等式:

的下界,希望能使上面的不等式右方儘可能大。

相當大時,考慮,可以取,整理後得:

參考[编辑]