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

　さて今回から、グラフ理論における頂点カバー（以下VCと略す）、独立セット、クリークという問題についてしばらく説明します。今回は三つの問題の概念を簡単に説明します。そのあと、これら三つが本質的には同じ問題であるということを説明します。それから、さらに、VC問題がNP完全であることを３SATを使って証明するという流れになります。それは、次回、次々回、次々々回、もしかしたら次々々々回ということになっていくと思います。
　
　では説明に入りましょう。
　
　ちょっとその前に言いたいことがあるんです。よく考えたらですね、３SATを論理式にして、サーキットで表わせば、その問題は、そのままNP完全ですね。実は、この前気づきました。どうもすいません。テヘペロ(死語）
　
　では、どうして、頂点カバー他、このような問題を扱うのか、と言いますと、これらの問題を説明した後、モノトーンなサーキットということを説明していきますが、そのなかで小さなサーキットの部分を近似的にクリーク問題に置き換えて行き、これらの一般的なグラフの問題としてNP完全な問題を扱おう、という方法論がこれまで確立されているのです。それでは、今度こそ説明を始めましょう。
　
　あ、しまった。そうそう、ここで使う用語の説明をやらないといけなかった。
　
これまでこのブログでは集合論的な考え方を基調に説明を行ってきました。そこで、集合論的なサーキットの表現をここで定義しておきたいと思います。具体的には、ノード（頂点(Vertex))の集合をV={v1,v2,…,vn}と表わします。また枝（エッジ(Edge)）では、その集合をEと表わし、各枝は、たとえばノードv1,v2間の枝ならば{v1,v2}と表わします。また、このようなノードと枝をもつグラフGは、
　
　G=（V,E）
　
のように表わすこととします。サーキットとグラフの使い分けが少しややこしいかもしれませんが、我慢して付き合って下さいね。
　
　それでは、今度という今度こそ本題に入ります。
　
　・頂点カバー（Vertex Cover　略してVC）問題
　　　頂点カバー問題とは、あるグラフG=(V,E)が与えられたとしましょう。
　　　その時に任意の枝{u,v}∈Eを取ってきてもそのノードu,vのどちらかが
　　　頂点の部分集合V'⊆Vに含まれるようなV'が存在するかという問題です。

　　　もちろん、V'に含まれる頂点が多いほどそのようなV'は存在しやすくなります。
　　　したがって、最も小さい頂点の集合であるV'を求めるということも
　　　興味深い問題になってきます。こちらは、最小頂点被覆問題とも言い、
　　　NP完全以上の難しさであるNP困難であると言われています。
　　　（参考　http://ja.wikipedia.org/wiki/最小頂点被覆問題)

　

　・独立セット問題
　　　まず独立セットという概念を定義します。
　　　あるグラフG=(V,E)が与えられたとしましょう。
　　　その時に、頂点の部分集合V'⊆Vの任意の頂点の組u,vの間に
　　　エッジのない、すなわち、
　　
　　　　 　　　　　　{u,v}　∉　E
　　
　　　のとき、V'を独立セットと呼びます。
　
　　　独立セット問題とは、グラフG=(V,E)と自然数J≦|V|が与えられたとき、
　　　独立セットV'で|V’|≧Jとなるものが存在するか（あるいはしないか）を
　　　決定する問題ということになります。
　
　　　何となく分かると思いますが、独立セットは頂点カバーの頂点の補集合になります。
　　　したがって、上のVCの例では赤線に囲まれていない部分の頂点が
　　　独立セットであり、この場合少なくても|V’|=4ですので、Jが少なくても
　　　４を満たすということになります。

　　　この場合は、独立セットになる頂点の数が多い方が難しい問題となり、
　　　最も多い頂点の独立セットを求める問題がNP困難な問題となります。


　・クリーク(clique)問題
　　　クリークとはあるグラフG=(V,E)が与えられたとき、頂点の部分集合V'⊆Vが
　　　完全結合になっていることをクリークと言います。
　　　完全結合とは、二つの頂点同士を繋ぐエッジがある、頂点の集団のことです。
　　　エッジがあればその二つの頂点同士は完全に結合していますので、
　　　そういうことを大きさ2のクリークと言います。
　　　つまり、エッジがあればグラフG=(V,E)は、必ず大きさ2のクリークです。

　　　難しい言い方で定義するならば、クリークとは、ある頂点の部分集合
　　　V'⊆Vのどの二つの頂点u,v∈V'を取ってきてもエッジ{u,v}がグラフGの
　　　エッジの集合Eに属している（{u,v}∈E）ということになります。
　
　　　クリーク問題とは、グラフG=(V,E)と自然数J≦|V|が与えられたとき、
　　　クリークである頂点の集合V'で|V’|≧Jとなるものが存在するか
　　　（あるいはしないか）を決定する問題ということになります。
　
　　　また、もっとも大きな頂点の数を持つクリークを求める問題を
　　　最大クリーク問題と言い、最大クリーク問題もNP困難な問題と言われています。
　　　（参考：http://ja.wikipedia.org/wiki/最大クリーク問題）

　　　ちなみにクリークとは派閥とか徒党とかいう意味があるようです。
　　　確かに図を見るとそういう感じがありますよね。

ちなみに私はどちらかというと他人とのつながりがなく、いつもマスメディアにいじめられているという感じです。一般人なのに……。どうでも良いですよね、そういうことは、はい。では次回は上の三つが基本的には同じ問題になることをお話ししたいと思います。