共找到2條詞條名為厚度的結果 展開
- 語文
- 數學名詞
厚度
數學名詞
在圖論中，圖G的厚度是可以對G的邊緣進行分割的平面圖的最小數量。也就是說，如果存在k個平面圖的集合，它們具有相同的頂點集，且這些平面圖的並集是G，那麼G的厚度最多為k。換句話說，圖G的厚度是圖G的平面子圖的最小數目（而圖G是這幾個子圖的並集）。
因此，平面圖具有厚度1。厚度2的圖形稱為雙平面圖（biplanar graphs）。厚度的概念源於1962年FrankHarary的猜想：對於9點的任何圖形，它的本身或其互補圖形都是非平面的。這個問題等同於確定完整圖K9是否是雙平面的。佩特拉·穆澤爾、托馬斯·奧登塔爾和馬克·沙爾布羅特撰寫了關於1998年主題藝術狀況的綜合性調查。
n個頂點的完整圖形的厚度為：
只有當n=9,10的時候，其厚度為3。
除了一些例外，完整的二分圖的厚度通常為：
每個森林（在圖論中，森林由不相交的樹組成）都是平面的，每個平面圖都可以最多劃分成三個森林。因此，任何曲線G的厚度最多等於相同圖形的輪廓（輪廓是其邊緣可以分割成的森林的最小數量），至少等於輪廓除以3。G的厚度也在另一個標準圖不變數的恆定因子內，定義為子圖中G的最大值。如果n頂點圖具有厚度t，那麼它必然具有至多t（3n-6）輪廓，從而遵循其簡併度至多為6t-1。在另一方向，如果圖具有簡併D，則厚度最多為D。
厚度與同時嵌入的問題密切相關，如果兩個或更多個平面圖都共享相同的頂點集，則可以將所有這些圖形嵌入平面中，其中按照輪廓繪製為曲線，使得每個頂點在所有不同的圖形中具有相同的位置。然而，將邊緣繪製成直線段可能不會構造這樣的圖形。
曲線G的直線厚度或幾何厚度計算可分解成的平面圖的最小數量，受限於所有這些圖形可以與直邊同時繪製的數量。所有頂點都繪製成凸起的位置，形成圖形的圓形布局，又增加了額外的限制。然而，這三個厚度參數中的兩個總是處於彼此恆定的因子之內。
計算給定圖形的厚度是非常困難的，並且難以確定測試厚度是否至多為兩個。然而，與軸向的連接允許在多項式時間內將厚度近似為近似比3。