主题
Search

拉曼图


拉曼图是满足 拉曼定理 的图。换句话说,它是一个图 G,恰好有 2n-3图边,其中 nG图顶点 的数量,并且对于 G 的每个 子图,当子图有 n^'图顶点e^'图边 时,满足 e^'<=2n^'-3。按照惯例,单例图 K_1 通常被认为是拉曼图,即使它不满足条件 e=2n-3

拉曼图总是 连通的

LamanGraphs

节点数为 n=1, 2, ... 的简单拉曼图的数量是 1, 1, 1, 1, 3, 13, 70, 608, 7222, 110132, 2039273, 44176717, 1092493042, ... (OEIS A227117)。

拉曼图是最小刚性的,意思是移除任何一条边都会使得到的图在“一般位置”时变为柔性的。拉曼图构成了所谓的二维刚性拟阵的基础,这些拟阵描述了具有固定长度刚性边的无向图的自由度数量。

拉曼图在 R^2 中是“一般”刚性 的。换句话说,对于顶点处于 一般位置 的嵌入,它们是刚性的。然而,拉曼图可能具有柔性嵌入,对应于满足较低维度约束的顶点。例如,工具图 K_(3,3) (这是一个拉曼图)的嵌入在平面中是刚性的,除非它的六个顶点位于 圆锥曲线 上 (Bolker and Roth 1980, Maehara 1992)。

当从一个最初 刚性图 (具有相当对称性)中逐步移除顶点集合时,通常会出现拉曼图的柔性嵌入。


另请参阅

支撑多边形, 拉曼定理, 刚性图, 三角剖分图

使用 Wolfram|Alpha 探索

参考文献

Bolker, E. D. and Roth, B. "When is a Bipartite Graph a Rigid Framework?" Pacific J. Math. 90, 27-44, 1980.Capco, J.; Gallet, M.; Grasegger, G.; Koutschan, C.; Lubbes, N.; and Schicho, J. "The Number of Realizations of a Laman Graph." https://arxiv.org/abs/1701.05500. Nov. 2017.Daescu, O. and Kurdia, A. "Towards an Optimal Algorithm for Recognizing Laman Graphs." In Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09). IEEE, pp. 1-10, 2009. https://arxiv.org/abs/0801.2404.Henneberg, L. Die graphische Statik der starren Systeme. Leipzig, Germany: 1911.Laman, G. "On Graphs and Rigidity of Plane Skeletal Structures." J. Engineering Math. 4, 331-340, 1970.Maehara, H. "Distance Graphs in Euclidean Space." Ryukyu Math. J. 5, 33-51, 1992.Pollaczek-Geiringer, H. "Über die Gliederung ebener Fachwerke." Zeitschr. f. Angewandte Math. u. Mechanik 7, 58-72, 1992.Sloane, N. J. A. Sequence A227117 in "The On-Line Encyclopedia of Integer Sequences."

请按如下方式引用

Weisstein, Eric W. "拉曼图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/LamanGraph.html

主题分类