補グラフ（Complement Graph）について
補グラフ（complement graph）とは、与えられた無向グラフにおいて、辺の有無を反転させたグラフである。正式には、グラフ ( G = (V, E) ) に対して、その補グラフ ( \overline{G} = (V, \overline{E}) ) は次のように定義される：
[ \overline{E} = {(u, v) \mid u, v \in V, u \neq v, (u, v) \notin E }. ]
すなわち、補グラフ ( \overline{G} ) では、元のグラフ ( G ) で隣接していた頂点対は補グラフでは隣接せず、逆に隣接していなかった頂点対は補グラフでは隣接する。
- 自己補グラフ（self-complementary graph）: ( G ) と ( \overline{G} ) が同型（isomorphic）である場合、そのグラフを自己補グラフという。
- 完全グラフ（complete graph）の補グラフ: 頂点数 ( n ) の完全グラフ ( K_n ) の補グラフは、辺を持たない孤立点の集合となる。
- 空グラフ（empty graph）の補グラフ: 辺を一切持たないグラフ（空グラフ）の補グラフは完全グラフ ( K_n ) になる。
- 補グラフの補グラフ: ( \overline{\overline{G}} = G ) となる。つまり、補グラフを二重に取ると元のグラフに戻る。
補グラフの概念は、グラフ理論の多くの分野で応用される。
- グラフの対称性の研究: 自己補グラフの分類や、補グラフを用いた非対称グラフの構成。
- ネットワーク理論: 社会ネットワークにおいて、直接的な関係がないが間接的に影響を与えるノードの分析。
- 計算複雑性: グラフの補グラフを用いた問題の変換により、NP完全問題の研究に役立つ。
パスグラフ ( P_5 )（5つの頂点が直線状に並んだグラフ）の補グラフは、元の辺がなかった頂点対がすべて結ばれるため、1つの完全グラフ ( K_2 ) と1つの三角形 ( K_3 ) に分解される。
4頂点のサイクルグラフ ( C_4 )（正方形状のグラフ）の補グラフは2本の辺を持つ離散グラフ（2つの ( K_2 ) の成分）となる。
補グラフは、グラフの構造を反転させる基本的な概念であり、グラフ理論のさまざまな分野で応用される。特に、グラフの対称性、ネットワークの解析、計算複雑性などに関わる重要なツールである。補グラフを用いた研究は、グラフの特性を深く理解する上で不可欠である。
