頂点カバー、独立セット、クリーク その２

今回は、頂点カバー問題（以下VCと略す)、独立セット問題、クリーク問題が本質的に同じ問題だということを示します。ところでここで、本質的に同じってなんでしょうか？この場合は、栄養の面から見れば、料理の見栄えがよかろうが悪かろうが、お腹の中に入ってしまえば同じ、ということとどこか似ています。つまり、数学的にNP完全な問題という面で同じである、として扱えるかどうかということが問題になってくるということです。毎年クリスマスを寂しく過ごした私が言うのもなんですけど、こういうところが女性に人気がないのだと思いますよ、数学。

さて、すでに、前回見たように、頂点カバー問題と独立セット問題は次のような関係にあります。

「あるグラフG=(V,E)が与えられた時、頂点カバーであるようなノードの部分集合V'⊆Vがあるとすると、独立セットであるような頂点の集合はV-V'で表わされる。」

下の図は、前回VCと独立セットを説明する時に使った図ですが、VCの集合に含まれていないノード同士は確かに直接繋がっていないノードの集合になっているのが分かると思います。

では、あるいVCは独立セット問題とクリーク問題はどのような関係にあるのでしょうか。

ここでは、分かりやすく頂点カバー問題とクリーク問題がNP完全と言うことから見て同じであるということを話します。これはやや複雑ですので、図をまず示しましょう。これは先ほど使った図を少しだけ補足説明のために修正したものですが、直感的に見て、VCの補集合である独立セットに属するノードを完全結合できるので、即ち、それでクリークと見なせると言えそうです。

では、もう少しだけ詳しく説明しましょう。まず、先ほども言いましたが、あるグラフG=(V,E)が与えられた時、VCであるような頂点の部分集合V'⊆Vがあるとします。このとき、エッジEcを次のように定義します。

　Ec={{u,v}|u,v∈V, u≠v, {u,v}∉E}

日本語で言えば、グラフGの異なる二つのノードのうちグラフGの枝集合Eに含まれていない枝の集合をEcと定義しますと言うことです。（上の図の赤線の部分）

この時グラフGcをGc={V,Ec}と定義すると、グラフG（とGc）のノード集合VからVCの集合V'∈Vを引いたもの（V-V')はクリークになっているということです。このノードの集合は、独立セットに一致しますよね。

こう考えるとわかりやすいかもしれません。VCでない頂点の集合は独立セットということでした。独立セット同士には直接に結合している枝がありません。集合Ecはその直接繋がっていないノード同士をつなげた枝の集合ですから、その時すなわち、独立セットとして存在していたノードの集合V-V'はその部分では完全結合になっている、ということです。

やっと、ここまで来ました。次回からは数回にわたって、これら三つが３SATに置き換えられることを（問題の複雑さの面という意味では本質的には同等の問題ですので）VCを使って証明します。今度こそさんさっさっと行けばいいのですけど。

2013年12月27日　7:24
　図に間違いがありました。本文の説明も一部間違っておりました。以上の部分を訂正いたしました。こころよりお詫びいたします。