補グラフ

グラフ理論の数学分野では、グラフGの補グラフまたは逆グラフは、同じ頂点を持つグラフHであり、2 つの異なる頂点がHで隣接（接続）しているのは、 Gで隣接していない場合のみである。つまり、グラフの補グラフを生成するには、完全なグラフを形成するために必要なすべての欠落したエッジを埋め、以前存在していたすべてのエッジを削除する。^{[ 1 ]}

グラフの補集合は、グラフの集合の補集合とは異なります。補集合となるのは辺のみです。

G = ( V , E )を単純無向グラフとし、P をV内の異なる頂点のすべてのペアから構成されるものとする。このとき、単純無向グラフH = ( V , P \ E )はGの補グラフである。 ^{[ 2 ]}ここで、P \ EはP内のEの相対補グラフである。

G = ( V , A )を単純有向グラフとし、O を V 内の異なる頂点のすべての順序対から構成されるものとする。このとき、単純有向グラフH = ( V , O \ A )はGの補グラフである。

G を単純な無向グラフ / 有向グラフとし、Kを同じ数の頂点を持つ完全な単純な無向グラフ / 有向グラフとする(つまり、対角線上の要素がゼロである場合を除き、すべての要素が 1 である)。${\displaystyle \mathbb {A} (G)}$そして${\displaystyle \mathbb {A} (K)}$GとKの隣接行列をそれぞれとします。このとき、Gの補行列H​​の隣接行列は次のようになります。${\displaystyle \mathbb {A} (H)=\mathbb {A} (K)-\mathbb {A} (G)}$。

多重グラフの場合、補集合は定義されません。

自己ループを許容する（ただし多重隣接は許容しない）グラフの場合、グラフGの補グラフは、 Gに自己ループを持たないすべての頂点に自己ループを追加し、 Gに自己ループを持つすべての頂点からその自己ループを削除し、それ以外は上記と同じ式を使用することで定義できます。ただし、この操作は単純グラフの場合とは異なり、自己ループを持たないグラフに適用すると、すべての頂点に自己ループを持つグラフになります。

いくつかのグラフ理論の概念は、相補性によって互いに関連している。

• 辺のないグラフの補グラフは完全グラフであり、その逆もまた然りである。
• グラフGの補グラフの任意の誘導部分グラフは、 G内の対応する誘導部分グラフの補グラフである。
• グラフにおける独立集合は、補グラフにおけるクリークであり、その逆もまた然りである。これは、独立集合が辺を持たない誘導部分グラフであり、クリークが完全な誘導部分グラフであるという、前述の2つの性質の特殊なケースである。
• グラフの自己同型群は、その補グラフの自己同型群である。
• 三角形を含まないグラフの補グラフは爪を含まないグラフであるが、^{[ 3 ]}逆は真ではない。

自己相補グラフとは、自身の補グラフと同型なグラフのことである。 ^{[ 1 ]}例としては、4頂点パスグラフや5頂点サイクルグラフなどが挙げられる。自己相補グラフの既知の特徴付けはない。

いくつかのグラフのクラスは自己相補的である。つまり、これらのクラスのいずれかに属するグラフの補グラフは、同じクラスに属する別のグラフである。

• 完全グラフとは、誘導部分グラフごとに彩色数が最大クリークのサイズに等しいグラフのことである。完全グラフの補グラフも完全グラフであるという事実は、ラースロー・ロヴァースの完全グラフ定理である。^{[ 4 ]}
• コグラフは、単一の頂点から非交和と補集合演算によって構築できるグラフとして定義されます。コグラフは自己補集合のグラフ族を形成します。つまり、任意のコグラフの補集合は、別の異なるコグラフです。複数の頂点を持つコグラフの場合、各補集合のグラフのうち、ちょうど1つが連結であり、コグラフの同等の定義の1つは、連結した誘導部分グラフのそれぞれが非連結の補集合を持つというものです。もう1つの自己補集合の定義は、コグラフは誘導部分グラフとして4頂点パスを持たないグラフであるというものです。^{[ 5 ]}
• もう一つの自己相補的なグラフのクラスは、分割グラフのクラスです。これは、頂点をクリークと独立集合に分割できるグラフです。同じ分割によって、補グラフにも独立集合とクリークが得られます。^{[ 6 ]}
• 閾値グラフは、独立頂点（隣接頂点を持たない頂点）または普遍頂点（以前に追加されたすべての頂点に隣接している頂点）を繰り返し追加することによって形成されるグラフです。これら 2 つの操作は相補的であり、自己相補的なグラフのクラスを生成します。^{[ 7 ]}

グラフ上のアルゴリズムの解析において、グラフとその補グラフの区別は重要です。なぜなら、疎グラフ（頂点のペアの数に比べてエッジの数が少ないグラフ）は一般に疎な補グラフを持たないため、与えられたグラフのエッジの数に比例する時間を要するアルゴリズムは、補グラフの明示的な表現で同じアルゴリズムを実行すると、はるかに長い時間を要する可能性があるからです。そのため、研究者たちは、補グラフを明示的に構築する必要のない暗黙的なグラフ表現を用いて、入力グラフの補グラフ上で標準的なグラフ計算を実行するアルゴリズムを研究してきました。特に、補グラフのサイズがはるかに大きい場合でも、与えられたグラフのサイズに比例する時間で、補グラフ上で深さ優先探索または幅優先探索をシミュレートすることが可能です。 ^{[ 8 ]}また、これらのシミュレーションを使用して、補グラフの接続性に関する他の特性を計算することも可能になります。^{[ 8 ] [ 9 ]}