極大クリークとグラフ彩色
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/05 07:45 UTC 版)
「弦グラフ」の記事における「極大クリークとグラフ彩色」の解説
perfect elimination orderingは、多項式時間で弦グラフの最大クリーク問題にも応用できる。最大クリーク問題は一般のグラフに対してはNP完全である。より一般には、弦グラフは極大クリークを高々頂点数に対して比例する数だけ持ちうるが、一般のグラフに対しては頂点数に対して極大クリークの個数は指数関数的に増大する。弦グラフの極大クリークを列挙するには、perfect elimination orderingを見つけ、その除去で用いるクリークが極大であるかを判定するだけである。 弦グラフのクリークは、双対弦グラフ（英語版）と呼ばれる。 弦グラフがパーフェクトであるとき、極大クリークが最大クリークとなる。この時、クリークの頂点数はグラフの彩色数（頂点彩色）と等しくなる。また、弦グラフはperfect elimination orderingの逆順に頂点を選択して、貪欲法を用いることで最適な彩色が可能である。 弦グラフの彩色多項式（英語版）は容易に計算できる。perfect elimination ordering v 1 , v 2 , … , v n {\displaystyle v_{1},v_{2},\ldots ,v_{n}} を導出し、Niをviまで削除した後のviの次数（隣接する頂点数）とする。例えば、最後の頂点に対するNであるNn、は他の頂点が除去された状態での隣接する頂点の数なので、Nn = 0である。彩色多項式は ( x − N 1 ) ( x − N 2 ) ⋯ ( x − N n ) {\displaystyle (x-N_{1})(x-N_{2})\cdots (x-N_{n})} であり、最終項は単にxであるため、この多項式はxで割り切れる。また、この性質は弦グラフの形から簡単に導ける。
※この「極大クリークとグラフ彩色」の解説は、「弦グラフ」の解説の一部です。
「極大クリークとグラフ彩色」を含む「弦グラフ」の記事については、「弦グラフ」の概要を参照ください。
- 極大クリークとグラフ彩色のページへのリンク
