Loading article…
グラフ理論において、無向グラフGのクリークグラフは、 G内のクリークの構造を表す別のグラフK ( G )です。
クリークグラフは少なくとも1968年には議論されており、[1]クリークグラフの特徴付けは1971年に行われました。[2]
正式な定義
グラフGのクリークは、 Gの頂点の集合Xであり、 X内の異なる頂点のすべてのペアがG内で隣接しているという特性を持ちます。グラフGの最大クリークは、 Gの頂点のクリークXであり、 X全体と少なくとも 1 つの他の頂点 を含むGの頂点のクリークY は存在しません。
グラフGが与えられたとき、そのクリークグラフK ( G ) は次のようなグラフである。
- K ( G )のすべての頂点はGの最大クリークを表す。
- K ( G )の2つの頂点は、 G内の基底クリークが少なくとも1つの頂点を共有している場合に隣接しています。
つまり、クリークグラフK ( G )はGの最大クリークの交差グラフである。[3]
特徴づけ
グラフHが別のグラフのクリークグラフK ( G ) であるための必要十分条件は、 H内のクリークの集合C が存在し、その和がHのすべての辺をカバーし、 C がヘリー族を形成する場合である。これは、S がCのサブセットであり、 Sのすべての 2 つの要素が空でない交差を持つという性質を持つ場合、 S自体も空でない交差を持つはずであることを意味する。ただし、C内のクリークは必ずしも最大クリークである必要はない。[2]
H = K ( G )のとき、 Cの各クリークがGの頂点vに対応し、v を含むGのクリークで構成されるこのタイプの族C が構築されることがあります。これらのクリークはすべて交差点にv を持っているため、 Hのクリークを形成します。このようにして構築された族C はヘリー特性を持ちます。なぜなら、ペアワイズ非空交差点を持つCの任意のサブ族はGのクリークに対応している必要があり、これはサブ族の交差点に属する最大クリークに拡張できるためです。[2]
逆に、H がHのすべての辺をカバーするクリークのヘリー族C を持つとき、それはグラフGのクリークグラフK ( G ) であり、その頂点はHの頂点とCの要素の非結合和である。このグラフG は、交差が空でないCのクリークの各ペア、およびHの頂点とそれを含む C のクリークの各ペアに対して辺を持つ。しかし、 Hの頂点のペアを接続する辺は含まない。このグラフGの最大クリークはそれぞれHの頂点 1 つとそれを含むCのすべてのクリークから構成され、それらの交差グラフは Hと同型である。[2]
しかし、この特徴づけは効率的なアルゴリズムにはつながらない。与えられたグラフがクリークグラフであるかどうかを認識する問題はNP完全である。[4]
参考文献
- ^ Hamelink, Ronald C. (1968). 「クリークグラフの部分的特徴付け」. Journal of Combinatorial Theory . 5 (2): 192–197. doi :10.1016/S0021-9800(68)80055-9.
- ^ abcd Roberts, Fred S. ; Spencer, Joel H. (1971). 「クリークグラフの特徴付け」. Journal of Combinatorial Theory . Series B. 10 (2): 102–108. doi :10.1016/0095-8956(71)90070-0.
- ^ Szwarcfiter, Jayme L. ; Bornstein, Claudson F. (1994). 「弦グラフとパスグラフのクリークグラフ」. SIAM Journal on Discrete Mathematics . 7 (2): 331–336. CiteSeerX 10.1.1.52.521 . doi :10.1137/S0895480191223191.
- ^ アルコン、リリアナ;ファリア、ルエルビオ。デ・フィゲイレド、セリーナ・MH。グティエレス、マリサ (2009)。 「クリークグラフ認識の複雑さ」。理論的なコンピューターサイエンス。410 (21–23): 2072–2083。土井：10.1016/j.tcs.2009.01.018。MR 2519298。
外部リンク
- グラフクラスとその包含に関する情報システム: クリークグラフ