選單圖示 主題
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) 總結了已知的成果,並給出了一些引數化圖族的閉合形式。


另請參閱

圖的維數

使用 探索

參考文獻

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." 來自 Web 資源。 https://mathworld.tw/MetricDimension.html

主題分類