ラマングラフ

グラフ理論において、ラマングラフは、平面内の棒と関節の最小限の剛性システムを記述する疎グラフの族である。正式には、ラマングラフはn頂点のグラフであり、すべてのkに対して、すべてのk頂点サブグラフは最大で 2 k  − 3 個の辺を持ち、グラフ全体がちょうど 2 n  − 3 個の辺を持つ。ラマングラフは、アムステルダム大学のジェラルド・ラマンにちなんで名付けられました。彼は 1970 年にラマングラフを使用して、剛性平面構造を特徴付けました。^[1] しかし、この特徴付け、つまりガイリンガー・ラマン定理は、1927 年にヒルダ・ガイリンガーによってすでに発見されていました。^[2]

ラマン グラフは剛性理論で生まれます。ラマン グラフの頂点をユークリッド平面の一般的な位置に配置すると、すべてのグラフ エッジの長さが維持されるユークリッド合同以外、すべての点が同時に連続的に動くことは一般にありません。グラフがこの意味で剛性を持つのは、そのすべての頂点にまたがるラマン サブグラフがある場合のみです。したがって、ラマン グラフはまさに最小限の剛性グラフであり、2 次元剛性マトロイドの基底を形成します。

平面上のn個の点が与えられた場合、それらの配置には 2 n 個の自由度があります (各点には 2 つの独立した座標があります)。しかし、剛体グラフには 3 個の自由度しかありません (1 つの頂点の位置と、その頂点の周りの残りのグラフの回転)。直感的には、グラフに固定長の辺を追加すると自由度の数が 1 つ減少するため、ラマン グラフの 2 n  − 3 個の辺は、初期の点配置の 2 n個の自由度を、剛体グラフの 3 個の自由度に減らします。ただし、2 n  − 3 個の辺を持つすべてのグラフが剛体であるわけではありません。ラマン グラフの定義では、どのサブグラフも辺が多すぎることはないという条件があるため、各辺は全体の自由度の数の削減に寄与し、他の辺によってすでに剛体であるサブグラフ内では無駄になりません。

尖った擬似三角形分割は、グラフの平面直線描画であり、外面が凸であること、すべての境界面が擬似三角形（凸頂点が3つだけの多角形）であること、すべての頂点に接続する辺の角度が180度未満であることなどの特性を持つ。尖った擬似三角形分割として描画できるグラフは、まさに平面ラマングラフである。^[3]ただし、ラマングラフには擬似三角形分割ではない平面埋め込みがあり、ユーティリティグラフ K _3,3などの平面ではないラマングラフも存在する。

Lee & Streinu (2008) および Streinu & Theran (2009) は、グラフが-スパースであるとは、頂点を持つすべての空でない部分グラフが最大で個の辺を持つ場合であり、-スパースで 個の辺を持つ場合を -タイトであると定義しています。したがって、彼らの表記法では、ラマングラフはまさに (2,3)-タイトグラフであり、ラマングラフの部分グラフはまさに (2,3)-スパースグラフです。同じ表記法を使用して、ツリー、疑似フォレスト、および境界付き樹木性グラフを含む、他の重要なスパースグラフのファミリを記述できます。^{[4] [5]}${\displaystyle (k,\ell )}$${\displaystyle n}$${\displaystyle kn-\ell}$${\displaystyle (k,\ell )}$${\displaystyle (k,\ell )}$${\displaystyle kn-\ell}$

この特性に基づいて、n^{頂点を持ち}辺のないグラフから始まり、各頂点に 2 つの小石を配置し、次の 2 種類の手順のシーケンスを実行してグラフのすべての辺を作成する「小石ゲーム」をシミュレートすることにより、n 頂点のラマン グラフをO ( n 2 ) の時間で認識できます。

• どちらも 2 つの小石を持つ任意の 2 つの頂点を接続する新しい有向エッジを作成し、新しいエッジの開始頂点から小石を 1 つ削除します。
• 最大で 1 つの小石がある頂点uから、少なくとも 1 つの小石がある別の頂点vにエッジが向いている場合は、小石をvからuに移動し、エッジを反転します。

これらの操作を使用して、与えられたグラフの向きを構築できる場合、そのグラフは必然的に (2,3)-スパースであり、その逆も同様です。ただし、時間 で実行されるより高速なアルゴリズムは、与えられたグラフの 1 つの辺を 2 倍にすると (2,2)-タイトなマルチグラフになるかどうか (つまり、2 つの辺が互いに素な全域木に分解できるかどうか) をテストし、次にこの分解を使用して、与えられたグラフがラマン グラフであるかどうかを確認することに基づいています。^[6]ネットワーク フロー技術を使用すると、時間 で、平面グラフがラマン グラフであるかどうかをより迅速にテストできます。^[7]${\displaystyle O(n^{3/2}{\sqrt {\log n}})}$ ${\displaystyle O(n\log^{3}n)}$

ラマンとガイリンガーの研究以前に、レブレヒト・ヘネベルグは2次元の最小剛性グラフ（つまりラマングラフ）を別の方法で特徴づけた。^[8]ヘネベルグは、2つ以上の頂点上の最小剛性グラフは、単一の辺から始めて、次の2種類の操作のシーケンスによって得られるグラフとまったく同じであることを示した。

1. グラフに新しい頂点と、それを既存の 2 つの頂点に接続するエッジを追加します。
2. グラフのエッジを細分化し、新しく形成された頂点を以前から存在していた 3 番目の頂点に接続するエッジを追加します。

特定のグラフを形成するこれらの操作のシーケンスは、グラフのヘネベルグ構成として知られています。たとえば、完全な二部グラフK _{3,3 は}、最初の操作で三角形を形成し、次に 2 番目の操作を適用して三角形の各辺を細分化し、各細分点を三角形の反対側の頂点に接続することで形成されます。