主题
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 中是完全可重构的。


另请参阅

通用全局刚性

使用 Wolfram|Alpha 探索

参考文献

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. "完全可重构图。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/FullyReconstructibleGraph.html

主题分类