Loading article…
数学の分野であるグラフ理論において、グラフGの補グラフまたは逆グラフとは、同じ頂点を持つグラフHのうち、 Hの2つの異なる頂点が隣接しているのは、Gで隣接していない場合のみである。つまり、グラフの補グラフを生成するには、完全グラフを形成するために必要なすべての欠落した辺を埋め、以前存在していたすべての辺を削除する。[1]
補集合はグラフの 補集合ではありません。辺のみが補集合になります。
意味
G = ( V , E )を単純グラフとし、K を V のすべての 2 要素サブセットから構成するとします。すると、H = ( V , K \ E )はGの補集合となり、[2] K \ EはKにおけるEの相対補集合となります。有向グラフの場合、補集合は、同じ頂点集合上の有向グラフとして、上記の式の集合Kの代わりにVのすべての 2 要素順序付きペアの集合を使用して、同じように定義できます。グラフの隣接行列Aに関して、 Qが同じ数の頂点を持つ完全グラフの隣接行列である場合(つまり、対角要素がゼロである以外はすべての要素が 1 である)、Aの補集合の隣接行列はQAです。
補グラフは多重グラフに対しては定義されません。自己ループを許可するグラフ（多重隣接は許可しない）では、 Gの補グラフは、 Gに自己ループがないすべての頂点に自己ループを追加し、それ以外の場合は上記と同じ式を使用することで定義できます。ただし、この操作は単純グラフの場合とは異なります。自己ループのないグラフに適用すると、すべての頂点に自己ループがあるグラフになるからです。
アプリケーションと例
いくつかのグラフ理論の概念は、相補性を通じて相互に関連しています。
- エッジのないグラフの補グラフは完全グラフであり、その逆も同様です。
- グラフGの補グラフの任意の誘導サブグラフは、 G内の対応する誘導サブグラフの補グラフです。
- グラフ内の独立集合は補グラフ内のクリークであり、その逆も同様です。これは前の 2 つの特性の特殊なケースであり、独立集合はエッジのない誘導サブグラフであり、クリークは完全な誘導サブグラフです。
- グラフの自己同型群はその補グラフの自己同型群です。
- すべての三角形のないグラフの補グラフは爪のないグラフであるが[3]、その逆は真ではない。
自己相補グラフとグラフクラス
自己相補グラフは、自身の補グラフと同型なグラフである。 [1]例としては、4頂点パスグラフや5頂点サイクルグラフなどがある。自己相補グラフの特徴づけは知られていない。
いくつかのグラフのクラスは自己補完的であり、これらのクラスのいずれかのグラフの補完グラフは同じクラスの別のグラフです。
- 完全グラフとは、すべての誘導部分グラフの彩色数が最大クリークのサイズに等しいグラフである。完全グラフの補グラフも完全であるという事実は、ラースロー・ロヴァースの完全グラフ定理である。[4]
- コグラフは、単一の頂点から互いに素な和と補数演算によって構築できるグラフとして定義されます。これらは自己補完的なグラフ族を形成します。つまり、任意のコグラフの補数は別の異なるコグラフです。複数の頂点を持つコグラフの場合、各補完ペアのグラフは 1 つだけ接続されており、コグラフの同等の定義の 1 つは、接続された誘導サブグラフのそれぞれに切断された補完があることです。もう 1 つの自己補完的な定義は、4 頂点パスの形で誘導サブグラフを持たないグラフであるということです。[5]
- グラフのもう一つの自己補完クラスは分割グラフのクラスであり、これは頂点をクリークと独立集合に分割できるグラフである。同じ分割により、補完グラフでは独立集合とクリークが得られる。[6]
- 閾値グラフは、独立頂点（隣接する頂点を持たない頂点）または普遍頂点（以前に追加されたすべての頂点に隣接する頂点）を繰り返し追加することによって形成されるグラフです。これら2つの操作は補完的であり、自己補完的なグラフのクラスを生成します。[7]
アルゴリズムの側面
グラフ上のアルゴリズムの分析では、グラフとその補グラフの区別が重要です。なぜなら、疎グラフ(頂点のペアの数に比べて辺の数が少ないグラフ) は一般に疎な補グラフを持たないため、与えられたグラフ上の辺の数に比例して時間がかかるアルゴリズムは、同じアルゴリズムを補グラフの明示的な表現で実行すると、はるかに長い時間がかかる可能性があるからです。そのため、研究者は、補グラフの明示的な構築を必要としない暗黙的なグラフ表現を使用して、入力グラフの補グラフ上で標準的なグラフ計算を実行するアルゴリズムを研究してきました。特に、補グラフのサイズがはるかに大きい場合でも、与えられたグラフのサイズに線形の時間で、補グラフ上で深さ優先探索または幅優先探索のいずれかをシミュレートできます。 [8]これらのシミュレーションを使用して、補グラフの接続性に関する他のプロパティを計算することもできます。[8] [9]
参考文献
- ^ ab ボンディ、ジョン・エイドリアン、マーティ、USR（1976）、グラフ理論とその応用、ノースホランド、p. 6、ISBN 0-444-19451-7。
- ^ Diestel, Reinhard (2005)、グラフ理論（第3版）、Springer、ISBN 3-540-26182-6電子版4ページ。
- ^ マリア・チュドノフスキー、ポール・シーモア(2005)、「クローフリーグラフの構造」(PDF)、組合せ論調査 2005、ロンドン数学会講義ノートシリーズ、第 327 巻、ケンブリッジ: ケンブリッジ大学出版局、pp. 153–171、MR 2187738。
- ^ Lovász, László (1972a)、「正規ハイパーグラフと完全グラフ予想」、離散数学、2 (3): 253–267、doi : 10.1016/0012-365X(72)90006-4。
- ^ コルニール、DG ; レルヒス、H.; スチュワート・バーリンガム、L. (1981)、「補数可約グラフ」、離散応用数学、3 (3): 163–174、doi : 10.1016/0166-218X(81)90013-5、MR 0619603。
- ^ ゴルビック、マーティン・チャールズ（1980）、アルゴリズムグラフ理論と完全グラフ、アカデミックプレス、定理6.1、p.150、ISBN 0-12-289260-7、MR 0562306。
- ^ ゴルビック、マーティン・チャールズ、ジェイミソン、ロバート・E. (2006)、「ランク許容度グラフクラス」、グラフ理論ジャーナル、52 (4): 317–340、doi :10.1002/jgt.20163、MR 2242832。
- ^ ab 伊藤 博; 横山 光夫 (1998)、「補グラフ上のグラフ検索と接続性判定のための線形時間アルゴリズム」、情報処理レター、66 (4): 209–213、doi :10.1016/S0020-0190(98)00071-4、MR 1629714。
- ^ Kao, Ming-Yang; Occhiogrosso, Neill; Teng, Shang-Hua (1999)、「密グラフと補数グラフのシンプルで効率的なグラフ圧縮スキーム」、Journal of Combinatorial Optimization、2 (4): 351–359、doi :10.1023/A:1009720402326、MR 1669307。