ぱーふぇくとぐらふとは何？わかりやすく解説 Weblio辞書

パーフェクトグラフ

読み方：ぱーふぇくとぐらふ
【英】：perfect graph

概要

グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ $G\,$ のすべての頂点誘導部分グラフに対して, その彩色数とクリーク数が等しいとき, $G\,$ をパーフェクトグラフと呼ぶ. パーフェクトグラフの補グラフもパーフェクトグラフとなることが知られている.

詳説

　1960年代初頭にベルジュ (C. Berge) は, パーフェクトグラフ (perfect graph) の概念やそれに関する予想を提案した. 予想の一つ「パーフェクトグラフの補グラフもパーフェクトである」は, 1972年にロバース(L. Lovász) によって解かれた. それよりも強い予想であるパーフェクトグラフ予想 (perfect graph conjecture) (後述) は近年ついに証明された [3]. パーフェクトグラフは半正定値計画問題の研究の源流の一つでもあり, 計算の複雑さの観点からも興味深いグラフのクラスである. パーフェクトグラフに関しては参考文献にあげた図書 [1, 4] が詳しい.

　与えられたグラフ $G=(V,E)\,$ に対して, 集合 $K \subseteq V\,$ の任意の2頂点が隣接しているとき, $K\,$ を $G\,$ のクリーク (clique) とよぶ. 要素数最大のクリークを求める問題を $G\,$ に対する最大クリーク問題 (maximum clique problem) とよぶ. 最大クリークの大きさをクリーク数 (clique number) といい, $\omega(G)\,$ とかく. さらに, 頂点集合上の整数値重み $w = (w_i \mid i \in V) \in Z^V\,$ も導入し, 重みの総和を最大とするクリークを求める問題は次のような0-1整数計画問題

$\begin{array}{llll} \mbox{max.} & \sum_{i \in V} w_ix_i \\ \mbox{s. t.} & x_i + x_j \leq 1 & ((i,j) \not\in E), & \qquad (1)\\ & x_i \in \{0,1\} & (i \in V), \end{array}\,$

に定式化でき, この最適目的関数値を $\omega(G,w)\,$ とかく. 明かに $\omega(G) = \omega(G,1)\,$ である. クリークと対称的な性質, 任意の2要素が互いに隣接しない集合 $S \subseteq V\,$ を $G\,$ の安定集合 (stable set), あるいは独立集合 (independent set) という. 任意のクリークと安定集合の共通部分は高々1頂点であることを利用すると問題 (1)は安定集合全体のなす族 ${\mathcal S}\,$ を用いて次のようにかける.

$\begin{array}{llll} \mbox{max.} & \sum_{i \in V} w_ix_i \\ \mbox{s. t.} & \sum_{i\in S}x_i \leq 1 & (S \in {\mathcal S}), & \qquad (2)\\ & x_i \in \{0,1\} & (i \in V). \end{array}\,$

　グラフ $G=(V,E)\,$ に対して, 隣接する頂点同士が異なる色になるような彩色の仕方を頂点彩色 (vertex coloring) あるいは単に彩色(coloring)とよぶ. 最小色数の頂点彩色を求める問題をグラフ彩色問題 (graph coloring problem) の一種である頂点彩色問題(vertex coloring problem) とよび, このときの最小色数を彩色数 (coloring number) といい, $\chi(G)\,$ とかく. 彩色において同色の頂点の集合は安定集合であり, 頂点彩色問題は, $V \subseteq S_1 \cup \cdots \cup S_\ell\,$ となる安定集合の族 $\{S_1,\cdots,S_\ell\}\,$ で最小のものを求める問題とみなせる. さらに, 頂点集合上の重み $w = (w_i \mid i \in V) \in Z^V\,$ も導入し

$\begin{array}{llll} \mbox{min.} & \sum_{S \in {\mathcal S}} y_S \\ \mbox{s. t.} & \sum_{S \ni i}y_S \geq w_i & (i \in V), & \qquad (3)\\ & y_S \in Z_+ & (S \in {\mathcal S}), \end{array}\,$

という問題の最適目的関数値を $\chi(G,w)\,$ とかく(ただし ${\mathcal S}\,$ は $G\,$ の安定集合全体のなす族, $Z_+\,$ は非負整数全体を表す). 明かに $\chi(G,1)\,$ は彩色数 $\chi(G)\,$ と一致する. 問題 (3) の整数条件 $y_S \in Z_+\,$ を非負条件 $y_S \geq 0\,$ に置き換えた線形計画問題は, 問題 (2) の整数条件 $x_i \in \{0,1\}\,$ を非負条件 $x_i \geq 0\,$ で置き換えた線形計画問題の双対問題である. このことから次の関係が示せる.

$\omega(G,w) \leq \chi(G,w), \quad\,$ $(\,$ 特別な場合として $)\,$ $\quad \omega(G) \leq \chi(G). \qquad (4)\,$

$\omega(G) \leq \chi(G)\,$ は任意の彩色でクリークの各頂点は異なる色に塗られることより明かであろう.

　一般のグラフに対する最大クリーク問題や頂点彩色問題のNP困難性が知られている. すなわち, 多くの研究者はこれらの問題に対する多項式時間解法は存在しないと信じている. 不等式 (4) の間に入る量で多項式時間で計算出来るものにロバース数 (Lovász number)がある. (本来の定義とは異なるが) ロバース数 $\vartheta(G,w)\,$ は

$\vartheta(G,w) = \max \left\{ \begin{array}{l} \\ \\ \\ \\ \end{array}\right.$	$\bar{w}^{\top} B \bar{w} \; \begin{array}{\|l} \mbox{B:} \\ B_{ij} \\ \sum_i \end{array} \quad$	対称半正定値行列	$\left. \begin{array}{l} \\ \\ \\ \\ \end{array} \right\},$	$\bar{w}= \left( \begin{array}{c}\sqrt{w_1}\\ \vdots\\ \sqrt{w_n} \end{array} \right)\,$	$\quad (5)\,$
		$= 0 \;((i,j) \in E)\,$
		$B_{ii}= 1\,$