《パーフェクトグラフ》

【ぱーふぇくとぐらふ (perfect graph) 】

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

　与えられたグラフ$G=(V,E)\,$に対して, 集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle K \subseteq V\, } の任意の2頂点が隣接しているとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle K\, } を $G\,$ のクリーク (clique) とよぶ. 要素数最大のクリークを求める問題を $G\,$ に対する最大クリーク問題 (maximum clique problem) とよぶ. 最大クリークの大きさをクリーク数 (clique number) といい, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega(G)\, } とかく. さらに, 頂点集合上の整数値重み構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle w = (w_i \mid i \in V) \in Z^V\, } も導入し, 重みの総和を最大とするクリークを求める問題は次のような0-1整数計画問題

${\begin{array}{llll}{\mbox{max.}}&\sum _{i\in V}w_{i}x_{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)\,$ とかく. 明かに 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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_{i}x_{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)\,$とかく. 彩色において同色の頂点の集合は安定集合であり, 頂点彩色問題は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V \subseteq S_1 \cup \cdots \cup S_\ell\, } となる安定集合の族構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{S_1,\cdots,S_\ell\}\, } で最小のものを求める問題とみなせる. さらに, 頂点集合上の重み構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle w = (w_i \mid i \in V) \in Z^V\, } も導入し

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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}\, }

という問題の最適目的関数値を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \chi(G,w)\, } とかく(ただし構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal S}\, } は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } の安定集合全体のなす族, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle Z_+\, } は非負整数全体を表す). 明かに 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \chi(G,1)\, } は彩色数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \chi(G)\, } と一致する. 問題 (3) の整数条件構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y_S \in Z_+\, } を非負条件構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y_S \geq 0\, } に置き換えた線形計画問題は, 問題 (2) の整数条件構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_i \in \{0,1\}\, } を非負条件 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_i \geq 0\, } で置き換えた線形計画問題の双対問題である. このことから次の関係が示せる.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega(G,w) \leq \chi(G,w), \quad\, } $(\,$特別な場合として構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle )\, } 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \quad \omega(G) \leq \chi(G). \qquad (4)\, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega(G) \leq \chi(G)\, } は任意の彩色でクリークの各頂点は異なる色に塗られることより明かであろう.

　一般のグラフに対する最大クリーク問題や頂点彩色問題のNP困難性が知られている. すなわち, 多くの研究者はこれらの問題に対する多項式時間解法は存在しないと信じている. 不等式 (4) の間に入る量で多項式時間で計算出来るものにロバース数 (Lovász number)がある. (本来の定義とは異なるが) ロバース数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \vartheta(G,w)\, } は

$\vartheta (G,w)=\max \left\{{\bar {w}}^{\top }B{\bar {w}}\;{\begin{array}{|l}{\mbox{B: *}}\\B_{ij}=0\;((i,j)\in E)\\\sum _{i}B_{ii}=1\end{array}}\right\},\quad {\bar {w}}=\left({\begin{array}{c}{\sqrt {w_{1}}}\\\vdots \\{\sqrt {w_{n}}}\end{array}}\right)\,$ 　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \qquad (5)\, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {*}} 対称半正定値行列

と定義される. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } の補グラフを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{G}\, } と表すと,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega(G,w) \leq \vartheta(\overline{G},w) \leq \chi(G,w) \qquad (6)\, }

が成立する. グレッチェル (M. Grötschel), ロバースとシュライバー (A. Schrijver) は楕円体法でロバース数を多項式時間で求められることを示した. また (5) は半正定値計画問題なので, 半正定値計画問題に対する多項式時間解法でロバース数を求めることができる.

　グラフ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G=(V,E)\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U \subseteq V\, } に対して, 頂点集合を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U\, } とし, 両端点が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U\, } に含まれる辺全体を辺集合とする$G\,$の部分グラフを, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U\, } に誘導される頂点誘導部分グラフとよぶ. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } のすべての頂点誘導部分グラフ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G'\, } に対して 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega(G') = \chi(G')\, } を満たすグラフをパーフェクトグラフ (perfect graph) という. パーフェクトグラフを特徴付ける性質として次のようなものがある.

(a) 補グラフがパーフェクト,

(b) 任意の重みベクトル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle w=(w_i \in Z_+ \mid i \in V)\, } に対して $\omega (G,w)=\chi (G,w)\,$,

(c) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } のクリークの特性ベクトル全体の凸包が, 非負条件と問題 (2) の安定集合による不等式で表現できる,

(d) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } の任意の頂点誘導部分グラフ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G'\, } に対して 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha(G')\cdot\omega(G') \geq |V(G')|\, } が成立する, ただし$\alpha (G')\,$は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G'\, } の最大安定集合の要素数, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V(G')\, } は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G'\, } の頂点集合を表す,

(e) 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まない.

　(a) と (b) よりパーフェクトグラフに対して (6) は等号で成り立ち, 補グラフのロバース数を求めることで最大クリーク問題や頂点彩色問題が多項式時間で解けることが分かる. (c) は凸多面体を用いた特徴付けを与えている. (d) はロバースの与えた特徴付けで, この特徴付けより, 与えられたグラフがパーフェクトであるかの判定問題はco-NPに属する事が導かれる. この判定問題は多項式時間で解くことができる [2] (e) がパーフェクトグラフ予想と呼ばれていたものであり, 論文 [3] において証明され, 現在は強パーフェクトグラフ定理 (Strong Perfect Graph Theorem) と呼ばれる.

---

参考文献

[1] J. L. Ram{\'i}rez-Alfons{\'i}n and B. A. Reed, eds., Perfect Graphs, John Wiley & Sons, 2001.

[2] M. Chudnovsky, G. Cornu{\'e}jols, X. Liu, P. Seymour and K. Vuskovic, "Recognizing Berge Graphs," Combinatorica, 25 (2005), 143-186.

[3] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, "The Strong Perfect Graph Theorem," Ann. of Math., 164 (2006), 51-229.

[4] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.