基本介紹
剛性,平面度,稀疏度,構造,
剛性
完整的二分圖K3,3，一個非平面拉曼圖
拉曼圖出現在剛度理論中：如果將拉曼圖的頂點放在歐幾里得平面中，那么在一般位置上，除了歐幾里得全等以外，所有點通常都不會同時運動，從而保留了所有拉曼圖的長度。圖形邊緣。在且僅當圖具有跨越所有頂點的拉曼子圖時，圖才是剛性的。因此，拉曼圖恰好是最小剛度圖，它們構成了二維剛度擬陣的基礎。
如果給定了平面中的n個點，則它們的放置位置將具有2n個自由度（每個點具有兩個獨立的坐標），而剛性圖僅具有三個自由度（一個頂點和一個頂點的位置其餘圖圍繞該頂點的旋轉）。直觀地，在圖上添加固定長度的邊會使其自由度減少一個，因此拉曼圖中的2n-3個邊將初始點放置的2n自由度減少到a的三個自由度剛性圖。但是，並非每個具有2n-3個邊的圖都是剛性的。拉曼圖定義中的條件是，沒有子圖可以具有太多的邊，這確保了每個邊都有助於減少自由度的總數，並且不會因已經具有其他邊而在本身已經很剛性的子圖中浪費。
平面度
有角的偽三角形是圖形的平面直線圖，具有以下特徵：外表面是凸的，每個有界的表面都是偽三角形，一個只有三個凸頂點的多邊形，並且入射到每個頂點的邊跨越 角度小於180度。 可以繪製為尖偽三角形的圖恰好是平面拉曼圖。但是，拉曼圖具有非偽三角剖分的平面嵌入，並且存在非平面拉曼圖，例如效用圖K3,3。
稀疏度
Lee＆Streinu（2008）和Streinu＆Theran（2009）將圖定義為(k,l)-sparse，如果每個具有n個頂點的非空子圖最多具有(kn-l)個邊；如果是(k,l)-tight，則是(k,l)-sparse的，並且恰好具有kn-l個邊。因此，在其符號上，拉曼圖恰好是(2,3)-tight圖，而拉曼圖的子圖恰好是(2,3)-sparse圖。可以使用相同的符號來描述稀疏圖的其他重要族，包括樹木，偽森林和有界樹狀圖。
基於此特徵，可以通過模擬“卵石遊戲”來識別時間為O(
)的n點拉曼圖，該“卵石遊戲”以具有n個頂點且沒有邊的圖形開始，每個頂點上放置兩個卵石，並且執行以下兩種步驟的序列來創建圖形的所有邊緣：
1.創建一個新的有向邊，以連線兩個都有兩個小卵石的任意兩個頂點，並從新邊的起始頂點移除一個小卵石。
2.如果一條邊從一個最多包含一個卵石的頂點u指向另一個至少具有一個卵石的頂點v，則將一個卵石從v移到u並反轉邊緣。
如果這些操作可用於構造給定圖的方向，則它必然是(2,3)-sparse，反之亦然。但是，可以在O(
)的時間內運行更快的算法，根據測試給定圖的一個邊是否加倍是否會導致多圖為(2,2)-tight（等效地，它是否可以分解為兩個邊緣不相交的生成樹），然後使用此分解來檢查給定圖是否為拉曼圖。
構造
Moser主軸的Henneberg構造
勒布雷希特·亨內伯格（Lebrecht Henneberg）早在拉曼（Laman）的工作之前就以不同的方式描述了二維最小剛性圖（即拉曼圖）。 Henneberg表明，兩個或多個頂點上的最小剛度圖恰好是可以通過以下兩種類型的一系列操作從單個邊緣開始獲取的圖：
1.將新頂點以及將其連線到兩個先前存在的頂點的邊添加到圖中。
2.細分圖的邊緣，並添加將新形成的頂點連線到第三個先前存在的頂點的邊緣。
形成給定圖的這些操作的序列稱為圖的Henneberg構造。 例如，可以使用第一操作形成完整的二部圖K3,3來形成三角形，然後套用第二操作來細分三角形的每個邊緣，並將每個細分點與相對的三角形頂點相連。
