主題
Search

完全可重構圖


如果一個圖 G 可以從其 d 維測量多樣性中確定,則該圖 GC^d 中是完全可重構的。如果圖 GR^d 上且頂點數 n>=d+2 時是全域性剛性的,則圖 GC^d 中是完全可重構的 (Garamvölgyi et al. 2021)。完全可重構性問題已針對 d=1d=2 得到解決 (Bernstein and Gortler 2022)。

對於在三個或更多頂點上且沒有孤立頂點的圖 G,圖 GC^1 中是完全可重構的,當且僅當它是 3-連通的 (Garamvölgyi et al. 2021, Bernstein and Gortler 2022)。

對於在四個或更多頂點上的圖 G,圖 GC^2 中是完全可重構的,當且僅當G 在二維中是通用全域性剛性的 (Garamvölgyi et al. 2021, Bernstein and Gortler 2022)。

d=3 時圖中完全可重構性的性質尚未完全確定,儘管已知一些必要條件和一些充分條件。Bernstein 和 Gortler (2022) 表明,完全二分圖 K_(5,5)C^3 中是完全可重構的。


另請參閱

通用全域性剛性

使用 探索

參考文獻

Bernstein, D. I. and Gortler, S. J. "K_(5,5)C^3 中是完全可重構的。" 已提交至Disc. Math., 2022.Garamvölgyi, D.; Gortler, S. J.; and Jordán, J. "全域性剛性圖是完全可重構的。" 2021 年 5 月 10 日。 https://arxiv.org/abs/2105.04363.

請引用為

Weisstein, Eric W. "完全可重構圖。" 來自 網路資源。 https://mathworld.tw/FullyReconstructibleGraph.html

主題分類