主題
Search

圖的維度


維度 e(G),也稱為圖的歐幾里得維度(例如,Buckley 和 Harary 1988),是歐幾里得空間 n 的最小維度 n,其中圖 G 可以被嵌入,且每條邊的長度都等於 1,每個頂點的位置都不同(但邊可以交叉或重疊,點可以位於不與其關聯的邊上;Erdős et al. 1965)。

任何最大頂點度為 Delta 的連通圖 connected graph 的圖維度最多為 Delta,除了效用圖 utility graph K_(3,3) (Frankl et al. 2018)。此外,任何色數為 k 的圖 chromatic number 的圖維度最多為 2k。這可以透過將空間劃分為 k 個正交的二維平面來實現,然後在每個平面上,將具有一種顏色的頂點放置在以平面原點為中心的半徑為 1/sqrt(2) 的圓上(因此所有點的平方範數為 1/2)(J. Tan,私人通訊,2021 年 10 月 26 日)。

對於任何非空圖 G,圖的笛卡爾積 graph Cartesian product 滿足

 e(G square K_2)={e(g)   if e(G)>=2; e(G)+1   if e(G)=0 or 1
(1)

(Erdős et al. 1965, Buckley 和 Harary 1988)。雖然這兩個參考文獻都宣告該定理適用於“任何”圖,但如果將 G 視為空圖 empty graph K^__n,則 K^__n square K_2 同構於梯子圖 ladder rung graph nP_2。然而,對於 n>1e(K^__n)=1(因為根據圖維度的定義,頂點不能重疊),並且 e(nP_2)=1,因為每個 n 路徑都可以放置在 1 維線上。

單點圖 singleton graph K_1 的圖維度為 e(K_1)=0,路徑圖 path graphs P_n(對於 n>1)的圖維度為 e(P_n)=1,一般來說,任何維度為 2 或更小的圖都被稱為單位距離圖 unit-distance graph

完全圖 complete graph K_n 的維度是 e(K_n)=n-1 (Erdős et al. 1965, Buckley 和 Harary 1988)。對於完全二分圖 complete bipartite graph K_(m,n),其中 <=n

 e(K_(m,n))={1   for m=n=1; 2   for m=n=2 or m=1, n>1; 3   for m=2, n>2; 4   m,n>=3
(2)

(Erdős et al. 1965, Buckley 和 Harary 1988)。

K_n-e 的維度由 e(K_n-e)=n-2 給出,對於 n>=3 (Erdős et al. 1965)。

超立方體圖 hypercube graph Q_n 的維度為 e(Q_n)=2,對於 n>=2 (Erdős et al. 1965)。

輪圖 wheel graph W_n 的圖維度對於 n=7 為 2(因此是單位距離圖 unit-distance),否則為 3(因此不是單位距離圖)(Erdős et al. 1965, Buckley 和 Harary 1988)。

下表總結了各種引數化圖族的圖維度。


另請參閱

度量維度, 單位距離圖

使用 探索

參考文獻

Buckley, F. 和 Harary, F. "On the Euclidean Dimension of a Wheel." Graphs and Combin. 4, 23-30, 1988.Erdős, P.; Harary, F.; 和 Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.Frankl, N.; Kupavskii, A.; Swanepoel, K. J. "Embedding Graphs in Euclidean Space." 2018年2月12日. https://arxiv.org/abs/1802.03092.

請將此頁引用為

Weisstein, Eric W. "圖的維度。" 來自 --一個 資源。 https://mathworld.tw/GraphDimension.html

學科分類