主题
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)。

下表总结了各种参数化图族的图维度。


另请参阅

度量维度, 单位距离图

使用 Wolfram|Alpha 探索

参考文献

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. "图的维度。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/GraphDimension.html

学科分类