厚度[數學名詞]

簡介

在圖論中，圖G的厚度是可以對G的邊緣進行分割的平面圖的最小數量。 也就是說，如果存在k個平面圖的集合，它們具有相同的頂點集，且這些平面圖的並集是G，那么G的厚度最多為k。換句話說，圖G的厚度是圖G的平面子圖的最小數目（而圖G是這幾個子圖的並集）。

因此，平面圖具有厚度1。厚度2的圖形稱為雙平面圖（ biplanar graphs）。 厚度的概念源於1962年Frank Harary的猜想：對於9點的任何圖形，它的本身或其互補圖形都是非平面的。 這個問題等同於確定完整圖K是否是雙平面的。佩特拉·穆澤爾、托馬斯·奧登塔爾和馬克·沙爾布羅特撰寫了關於1998年主題藝術狀況的綜合性調查。

具體的圖

n個頂點K的完整圖形的厚度為：

厚度[數學名詞]

只有當n = 9,10的時候，其厚度為3。

除了一些例外，完整的二分圖K的厚度通常為：

厚度[數學名詞]

相關問題

每個森林（在圖論中，森林由不相交的樹組成）都是平面的，每個平面圖都可以最多劃分成三個森林。 因此，任何曲線G的厚度最多等於相同圖形的輪廓（輪廓是其邊緣可以分割成的森林的最小數量），至少等於輪廓除以3。G的厚度也在另一個標準圖不變數的恆定因子內，定義為子圖中G的最大值。 如果n頂點圖具有厚度t，那么它必然具有至多t（3n-6）輪廓，從而遵循其簡併度至多為6t -1。在另一方向，如果圖具有簡併D，則厚度最多為D。

厚度與同時嵌入的問題密切相關，如果兩個或更多個平面圖都共享相同的頂點集，則可以將所有這些圖形嵌入平面中，其中按照輪廓繪製為曲線，使得每個頂點在所有不同的圖形中具有相同的位置。 然而，將邊緣繪製成直線段可能不會構造這樣的圖形。

曲線G的直線厚度或幾何厚度計算可分解成的平面圖的最小數量，受限於所有這些圖形可以與直邊同時繪製的數量。所有頂點都繪製成凸起的位置，形成圖形的圓形布局，又增加了額外的限制。 然而，這三個厚度參數中的兩個總是處於彼此恆定的因子之內。

計算複雜性

計算給定圖形的厚度是非常困難的，並且難以確定測試厚度是否至多為兩個。然而，與軸向的連線允許在多項式時間內將厚度近似為近似比3。