グラフ理論において、コグラフ（）、または補可約グラフ（）、P4フリーグラフ（）とは、単一の頂点グラフ K1 から補グラフ化とによって生成できるグラフのことである。すなわち、コグラフの族は、K1 を含み、補グラフ化と非交和の下で閉じているグラフの最小のクラスである。この再帰的な生成規則から定義されるクラスは、4つの頂点上の道 P4 を誘導部分グラフとして含まないグラフのクラスと一致することが知られており、これが「P4フリーグラフ」という別名の由来である。
コグラフは1970年代以降、複数の著者によって独立に発見されてきた。初期の文献には 、、、 などがある。それらはまた、D*-グラフ、遺伝的デイシーグラフ（直交モジュラー束に関するJames C. Dacey Jr.の関連研究にちなむ）、および2-パリティグラフとも呼ばれてきた。
これらは、ラベル付き木によって簡潔に表現でき、より一般的なグラフクラスでは困難な最大クリークの発見などの多くの問題をアルゴリズム的に効率よく解くために用いることができる、非交和と補グラフの操作を含む単純な構造的分解を持つ。
コグラフの特殊な種類には、完全グラフ、完全2部グラフ、、が含まれる。コグラフはまた、、置換グラフ、、理想グラフの特殊なケースでもある。
定義 再帰的構成 任意のコグラフは以下の規則を用いて構成できる。 任意の単一頂点グラフはコグラフである。 がコグラフならば、その補グラフ もコグラフである。 と がコグラフならば、その非交和 もコグラフである。
コグラフは、単一頂点グラフから出発してこれらの操作を用いて構成できるグラフとして定義されることもある。
あるいは、補グラフの操作を用いる代わりに、非交和 を形成し、次に の頂点と の頂点のすべてのペアの間に辺を追加することからなるを用いることもできる。
その他の特徴付け コグラフのいくつかの代替的な特徴付けを与えることができる。それらの中には以下のものが含まれる。
コグラフは、4つの頂点上の（したがって長さ3の）道 P4 を誘導部分グラフとして含まないグラフである。すなわち、グラフがコグラフであるための必要十分条件は、任意の4つの頂点 について、 および がグラフの辺であるならば、 または の少なくとも一つも辺であることである。 コグラフは、すべての誘導部分グラフが、任意の極大クリークが任意のと単一の頂点で交わるという性質を持つグラフである。 コグラフは、すべての自明でない誘導部分グラフが、同じ近傍を持つ頂点を少なくとも2つ持つグラフである。 コグラフは、すべての自明でない連結な誘導部分グラフが、非連結な補グラフを持つグラフである。 コグラフは、すべての連結な誘導部分グラフが2以下のを持つグラフである。 コグラフは、すべてのが直径2以下のであるグラフである。 コグラフは、が2以下のグラフである。 コグラフは、のである。 コグラフは、の置換グラフである。 コグラフは、その最小がすべてであるグラフである。 コグラフは、に、すなわちすべての誘導部分グラフのすべてのが最適数の色を用いるグラフである。 グラフがコグラフであるための必要十分条件は、そのグラフのすべての頂点順序がとなることである。なぜなら、P4 を持たないことは、どの頂点順序においても完全順序に対する障害が存在しないことを意味するからである。
コツリー
コツリー（）とは、内部ノードが0と1の数字でラベル付けされた木である。すべてのコツリー T は、T の葉を頂点として持ち、T の各ノードを根とする部分木が、そのノードから派生する葉の集合によって定義される G の誘導部分グラフに対応するコグラフ G を定義する。 単一の葉ノードからなる部分木は、単一の頂点を持つ誘導部分グラフに対応する。 0とラベル付けされたノードを根とする部分木は、そのノードの子によって定義される部分グラフの和に対応する。 1とラベル付けされたノードを根とする部分木は、そのノードの子によって定義される部分グラフの結び（join）に対応する。すなわち、和を形成し、異なる部分木の葉に対応するすべての2頂点間に辺を追加する。あるいは、グラフの集合の結びは、各グラフの補グラフを取り、それらの補グラフの和を形成し、次にその結果得られた和の補グラフを取ることによって形成されるとみなすこともできる。 コツリーから形成されるコグラフを記述する等価な方法は、2つの頂点が辺によって結ばれているための必要十分条件が、対応する葉のが1とラベル付けされていることである、というものである。逆に、すべてのコグラフはこのようにしてコツリーによって表現することができる。この木の任意の根-葉パス上のラベルが0と1の間で交互になることを要求する場合、この表現は一意となる。
計算上の性質 コグラフは線形時間で認識でき、、、、またはを用いてコツリー表現を構築することができる。一度コツリー表現が構築されれば、多くのよく知られたグラフ問題は、コツリー上の単純なボトムアップ計算によって解くことができる。
例えば、コグラフにおいて最大クリークを見つけるには、コツリーの部分木によって表される各部分グラフの最大クリークをボトムアップ順に計算する。0とラベル付けされたノードの場合、最大クリークはそのノードの子について計算されたクリークの中での最大のものである。1とラベル付けされたノードの場合、最大クリークはそのノードの子について計算されたクリークの和であり、子のクリークのサイズの合計に等しいサイズを持つ。このように、コツリーの各ノードに格納された値を交互に最大化したり合計したりすることによって、最大クリークのサイズを計算でき、交互に最大化したり和集合を取ったりすることによって、最大クリーク自体を構成することができる。同様のボトムアップの木計算により、コグラフのコツリー表現から、、頂点彩色数、最大クリーク被覆、およびハミルトン性（すなわちハミルトン閉路の存在）を線形時間で計算することができる。コグラフは有界なクリーク幅を持つため、を用いて、コグラフ上のモナディック二階 (MSO1) における任意の性質を線形時間で判定できる。
与えられたグラフがコグラフから k 頂点および／または t 辺離れているかどうかを判定する問題は、である。グラフが k 辺の削除によってコグラフにできるかどうかの決定は O*(2.562k) 時間で解くことができ、k 辺の編集によってコグラフにできるかどうかは O*(4.612k) 時間で解くことができる。もしグラフから k 頂点を削除することによってグラフの最大の誘導コグラフ部分グラフを見つけられるならば、それは O*(3.115k) 時間で見つけることができる。
2つのコグラフが同型であるための必要十分条件は、それらのコツリー（同じラベルを持つ2つの隣接する頂点が存在しない標準形において）が同型であることである。この等価性により、それらのコツリーを構築し、ラベル付き木に対する線形時間同型判定アルゴリズムを適用することによって、2つのコグラフが同型であるかどうかを線形時間で決定することができる。
もし H がコグラフ G の誘導部分グラフであるならば、H 自体もコグラフである。H のコツリーは、G のコツリーからいくつかの葉を取り除き、次に子が1つしかないノードを抑制（削除して辺を繋ぎ直すこと）することによって形成できる。クラスカルの木定理から、誘導部分グラフであるという関係は、コグラフ上の（well-quasi-ordering）であることが従う。したがって、もしコグラフの部分族（平面的コグラフなど）が誘導部分グラフの操作の下で閉じているならば、それは有限個の禁止部分グラフを持つ。計算上、これは、与えられたグラフのコツリーに対するボトムアップ計算を用いて、それがこれらの禁止部分グラフのいずれかを含んでいるかどうかを判定することにより、そのような部分族に属しているかどうかの判定を線形時間で実行できることを意味する。しかしながら、2つのコグラフのサイズが両方とも変数である場合、一方が他方の誘導部分グラフであるかどうかの判定はNP完全である。
コグラフは、を認識するためのアルゴリズムにおいて重要な役割を果たす。
入力がコグラフに制限された場合、いくつかの計数問題も扱いやすくなる。例えば、コグラフにおけるクリークの数や最大クリークの数を数える多項式時間アルゴリズムが存在する。
列挙 頂点数 n の連結コグラフの数は、n = 1, 2, 3, ... について以下のようになる。
1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ...
n > 1 については、同じ数の非連結コグラフが存在する。これは、頂点数 n の非連結コグラフが、頂点数 n の連結コグラフの補グラフとして一対一に対応することによる。実際、コグラフの定義より、非自明な（頂点数2以上の）任意のコグラフについて、それ自身とその補グラフのうち、ちょうど一方のみが連結となる。
関連するグラフ族 部分クラス すべての完全グラフ はコグラフであり、単一の1-ノードと 個の葉からなるコツリーを持つ。同様に、すべての完全2部グラフ はコグラフである。そのコツリーは、2つの0-ノードの子（1つは 個の葉の子を持ち、もう1つは 個の葉の子を持つ）を持つ1-ノードを根としている。
は、同じサイズの独立集合の族の結びによって形成することができる。したがって、それもまたコグラフであり、各独立集合に対応する子の0-ノードを持つ1-ノードを根とするコツリーを持つ。
すべてのもまたコグラフである。閾値グラフは、以前のすべての頂点に接続された頂点、またはどの頂点にも接続されていない頂点を繰り返し追加することによって形成できる。そのような各操作は、コツリーを形成できる非交和または結びの操作の1つである。
上位クラス すべてのクリークと極大独立集合が空でない交わりを持つという性質によるコグラフの特徴付けは、すべての誘導部分グラフがすべての極大クリークと交わる独立集合を含むという、強理想グラフの定義性質のより強いバージョンである。コグラフにおいては、すべての極大独立集合がすべての極大クリークと交わる。したがって、すべてのコグラフは強理想グラフである。
コグラフが P4 フリーであるという事実は、それらがであることを意味する。実際、コグラフのすべての頂点順序は完全順序であり、これはさらに、コツリー分解を必要とせず、任意の貪欲彩色を用いて最大クリークの発見と最小彩色を線形時間で見つけることができることを意味している。
すべてのコグラフはである。つまり、コグラフにおけるすべての誘導パスは最短路である。コグラフは、距離遺伝グラフの中で、各連結成分において直径が最大2であるものとして特徴付けられる。
すべてのコグラフはまた、のでもある。これは、コグラフを構成する非交和と結びの操作を、半順序上の非交和と順序和の操作に置き換えることによって得られる。
強理想グラフ、完全順序付け可能グラフ、距離遺伝グラフ、および比較可能グラフはすべて理想グラフであるため、コグラフもまた理想グラフである。
注釈
参考文献
. . . . . . . . . . . . . . .
. . . .
. . .
外部リンク