数学の一分野であるグラフ理論において、無向グラフGの単体グラフκ( G )はそれ自体がグラフであり、G内の各クリーク（互いに隣接する頂点の集合）ごとに1つのノードが存在する。κ( G )の2つのノードは、対応する2つのクリークが単一の頂点の有無で異なる場合、辺によって連結される。
空集合は、クリークグラフを形成するために使用されるGのクリークの1つとして含まれます。これは、1つの頂点からなるすべての集合、および隣接する2つの頂点からなるすべての集合も同様です。したがって、単体グラフはG自身の細分を内包します。完全グラフの単体グラフは超立方体グラフであり、長さが4以上のサイクルグラフの単体グラフはギアグラフです。パスグラフの補グラフの単体グラフはフィボナッチキューブです。
Gの完全なサブグラフには、メディアン代数の構造を与えることができます。つまり、3 つのクリークA、B、Cのメディアンは、3 つのクリークの過半数に属する頂点によって形成されます。 [1]このメディアンセットに属する任意の 2 つの頂点は、両方ともA、B、Cの少なくとも 1 つに属している必要があり、したがってエッジでリンクされている必要があります。そのため、3 つのクリークのメディアン自体がクリークです。単体グラフは、このメディアン代数構造に対応するメディアングラフです。 Gが二部グラフの補グラフである場合、 Gのクリークには分配格子[2]としてより強い構造を与えることができ、この場合、単体グラフは格子のグラフです。より一般的なメディアングラフと同様に、すべての単体グラフ自体は二部です。
単体グラフは、 Gのクリーク複体 X ( G )の各単体に対して1つの頂点を持ち、対応する2つの単体の一方が他方の面である場合、2つの頂点は辺で結ばれる。したがって、オブジェクト（単体グラフの頂点、X ( G )の単体）とオブジェクト間の関係（単体グラフの辺、X ( G )の単体間の包含関係）は、 X ( G )とκ( G )の間で1対1に対応する。
単体グラフは Bandelt & van de Vel (1989) [3]によって導入されました。彼らは、単体グラフに立方体が存在しないのは、基礎となるグラフが三角形を持たない場合のみであることを観察しました。また、基礎となるグラフの彩色数は、単体グラフをn本の木の直積に等長的に埋め込むことができる最小の数nに等しいことを示し、高い彩色数を持つ三角形を持たないグラフが存在する結果として、有限個の実木の積に埋め込むことのできない2 次元位相的メディアン代数が存在することを示しまし た。Imrich、Klavžar、Mulder (1999) も単体グラフを使用して、グラフが三角形を持たないかどうか、またはメディアン グラフであるかどうかをテストすることは、同様に速く実行できることの証明を行っています。
注記
- ^ バルテルミー、ルクレール、モンジャルデ (1986)、200 ページ。
- ^ プロップ（1997年）。
- ^ Imrich、Klavžar、Mulder (1999) は、単体グラフの導入は Bandelt と van de Vel による後の論文によるものだとしているが、これは間違いのようだ。
参考文献
- Bandelt, H.-J.; Chepoi, V. (2008)「計量グラフ理論と幾何学：概説」Goodman, JE ; Pach, J.; Pollack, R. (編)『離散幾何学と計算幾何学の概説：20年後』Contemp. Math., vol. 453, Providence, RI: AMS, pp. 49– 86。
- Bandelt, H.-J.; van de Vel, M. (1989)、「デンドロンの積における位相的メディアン代数の埋め込み」、ロンドン数学会紀要、s3-58 (3): 439– 453、doi :10.1112/plms/s3-58.3.439、2013年4月15日時点のオリジナルよりアーカイブ。
- Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986)「分類の比較と合意の問題における順序集合の利用について」Journal of Classification , 3 (2): 187– 224, doi :10.1007/BF01894188, S2CID 6092438。
- イムリッチ、ウィルフリード; クラヴジャー、サンディ; マルダー、ヘンリー・マーティン (1999)、「メディアングラフと三角形のないグラフ」、SIAM Journal on Discrete Mathematics、12 (1): 111– 118、CiteSeerX 10.1.1.28.5906、doi :10.1137/S0895480197323494、MR 1666073。
- プロップ、ジェームズ（1997）、「有限分配格子のランダム要素の生成」、Electronic Journal of Combinatorics、4（2）R15、arXiv ： math.CO/9801066、doi ：10.37236 /1330、S2CID 13313188。
