菜单图标 主题
Search

度量维数


度量维数 beta(G) (Tillquist 等人et al. 2021) 或 dim(G) (Tomescu 和 Javid 2007, Ali 等人 et al. 2016) 的图 G 是唯一标识所有其他节点所需的最小节点数,基于最短路径距离。更明确地说,根据 Foster-Greenwood 和 Uhl (2022),设 G 是一个有限连通图,其顶点集V。对于顶点 x,y in V图距离 d(x,y)xyG 之间最短路径的长度。考虑顶点子集 W subset= V,并将 W 中的顶点称为 “地标”。那么 W 被称为分辨集,如果对于每一对不同的顶点 x,y in V-W,都存在一个地标 w in W 使得 d(x,w)!=d(y,w)。最小可能大小的分辨集被称为 G 的度量基,G 的度量维数是度量基的大小。

Tillquist 等人et al. (2021) 总结了已知的成果,并给出了一些参数化图族的闭合形式。


另请参阅

图的维数

使用 Wolfram|Alpha 探索

参考文献

Ali, G.; Laila, R.; 和 Ali, M. "Metric Dimension of Some Families of Graph." Math. Sci. Lett. 5, 99-102, 2016.Foster-Greenwood, B. 和 Uhl, C. "Metric Dimension of a Diagonal Family of Generalized Hamming Graphs." 2 Aug 2022. https://arxiv.org/abs/2208.01519.Harary, F. 和 Melter, R. A. "On the Metric Dimension of a Graph." Ars Combin. 2, 191-195, 1976.Slater, P. J. "Leaves of Trees." Congr. Numer., No. 14, 549-559, 1975.Tillquist, R. C.; Frongillo, R. M.; Lladser, M. .E "Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and its Applications." https://arxiv.org/abs/2104.07201.Tomescu, I. 和 Javid, I. "On the Metric Dimension of the Jahangir Graph." Bull. Math. Soc. Sci. Math. Roumainie 50, 371-376, 2007.

请引用为

Weisstein, Eric W. "Metric Dimension." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/MetricDimension.html

主题分类