主題
Search

拉曼圖

拉曼圖是滿足 拉曼定理 的圖。換句話說，它是一個圖 G，恰好有 2n-3 條 圖邊，其中 n 是 G 中 圖頂點 的數量，並且對於 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)。

當從一個最初 剛性圖 （具有相當對稱性）中逐步移除頂點集合時，通常會出現拉曼圖的柔性嵌入。

另請參閱

支撐多邊形, 拉曼定理, 剛性圖, 三角剖分圖

使用 探索

參考文獻

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

主題分類