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

今回は、頂点カバー問題（以下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
　図に間違いがありました。本文の説明も一部間違っておりました。以上の部分を訂正いたしました。こころよりお詫びいたします。

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

　さて今回から、グラフ理論における頂点カバー（以下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/最大クリーク問題）

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

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

サーキットというグラフ その２

前回まで、簡単にグラフ理論にふれ、サーキットというグラフについて定義しました。今回はもう少しだけ詳しく説明し、そのほかの用語の解説の続きを行います。
　
ところで、ここまでこのブログではいろいろなアメリカのＩＴ企業との関連について（少し無理矢理）触れてきましたが、グラフ理論といえばグーグル。Web上のページをノード、リンクを枝とみなし、インデグリーの数から割り出した順位を、ベージランクと名付けて検索結果における重要度と見なすというのが、基本的なアルゴリズムというのは有名です。私でも知ってますし。そういえば、前回、枝をリンク（link）とも言うと説明しましたね。ちなみにページランクというのは、グーグルの創業者のラリー・ページさんの名前と掛けてあるそうです。ググると分かります。

　

さて、ググってもなかなか出てこない私のブログですが、お話を続けましょう。とほほ。

　

気を取り直して、もう一度サーキットの定義を再掲しましょう。

　

【サーキットの定義】
　いま、ブール変数x1 , … , xnが与えられているとします。グラフは、無サイクルな有方向グラフであり、
　　
　　（１）すべてのノードのインデグリーは0、もしくは、2である
　　　　（１－１）インデグリー0のノードをインプットもしくはリーフと呼ぶ
　　　　　　　　　（一般に、入力であるブール変数x1 , … , xn が相当する）
　　　　（１－２）インデグリー2のノードはゲート（gate）と呼ばれ
　　　　　　　　　∧（論理積）もしくは∨（論理和）が付加されている
　　（２）アウトデグリーの値は任意であるが、アウトデグリー0のノードが
　　　　　ただ一つだけあり、このノードのことをアウトプット(output)と呼ぶ
　
以上を満たすものをこれから、ブール変数x1 , … , xn上のブーリアン・サーキット（Boolean circuit）または、単にサーキットと呼ぶことにする、のでした。
　
ここで、いくつか例を挙げておきましょう。図1は以前「このブログを再開するに当たってのこれからの進め方」でサーキットの例として挙げた図です。インデグリーが２ではないものもありますが、これは、たとえば、図２のようにインデグリー２のグラフに変形できます（ここでは特に節の中（∨で結ばれたもの）だけを変形）。しかし、意味的には元のSAT形式を論理式として考えたときの式と同じでも、直感的な把握は図１の方が勝りますよね。というわけで、実際にはインデグリー２ではなくても意味的にインデグリー２のグラフにできるものも含めて以下サーキットと呼ぶことにします。

　
もう少しだけ、専門用語をお話しして一旦サーキットについての説明を終わりたいと思います。少し予定から先走りしている感じもありますし。
　
まず、論理式Ｆのリーフの数を定義してL(Ｆ)と表すことにします。サーキットＣではL(Ｃ)とも表すことができるのでしょうが、テキストではそこまでは触れていません。また、サーキットの縦の大きさ、これを深さ（depth)と呼びます。またサーキットＣのアウトプットからリーフまでの最大の段数と定義し、d(C)と表します。論理式Fに対しても同じようにd(F)と表わします。ここで、例を挙げるとサーキットで見ると図1と図2では意味的には同じ訳ですが、グラフの形（専門用語ではトポロジーとも言ったりしますが）がちがうわけで、それぞれのグラフの最大の深さをそれぞれ、d(C)=3、d(C)=4と表わすということになるのでちょっと注意が必要です。
　
え？論理式の深さd(F)ですか、さ、3じゃないですか、図１も図２もどちらも同じ論理式ですしね……

じ、実は、この後、論理式やサーキットを、ブール変数 x1 , … , xn から０か１かを与える（ブール）関数fと考えて、fと同じ値を返す論理式Ｆの中で最小のd(F)の値をd(f)とするという定義があるのです……。忘れてました。また、同様にリーフの数L(f)も同様に最小のL(F)の値とするというのがあるのです。随分と面倒ですよね。

グラフ理論についての簡単なお話

私が、電子工学出身と言うこともあり、グラフ理論においての用語は、そちら方面のいわゆる方言を用いているので、元々の数学をご専門とされている方にはなかなかわかりにくいかもしれません。それに、グラフ理論で閉路をサーキットという場合もあるようで、このブログで用いているブーリアン・サーキットと言葉が同じでも全く違った意味で使っているということになっています。

そこでWikipediaの記事をいくつか参考にしながら、標準的なグラフ理論に関しても少しだけ説明させていただきたいと思います（参考文献やそのリンクはその都度示すことにしますが、それ以外にも参考にしたものはこの記事の末尾に示します）

グラフ理論というのは、もともとは、一筆書きから出発したと言われています。その一筆書きにも原点がありまして、１８世紀、プロイセン王国の首都であったケーニヒスベルグに流れる大きな川に架かる７つの橋を同じ橋は二度通らずに一度にすべて渡れるか、という問題に端を発しているようです。これを、オイラーという人が、橋を辺、橋と橋を結ぶ部分を頂点と見なして、一筆書きという形で洗練させて、数学的に解方を示した、ということが元になっているようです（http://ja.m.wikipedia.org/wiki/一筆書き）

このあと、それが位相幾何学として発展していったために、頂点と辺という言葉が数学で一般的に使われるようになったものと思われます（http://ja.m.wikipedia.org/wiki/位相幾何学）

位相幾何学とは、簡単にいうと、すべての図形を点と線だけで分類しよう、という数学の分野です。たとえば、我々が平面に正三角形を書きます。そのとき、一つの角の大きさは６０度です。しかし、地球上にものすごく大きな正三角形を書いたとしたらどうでしょう。地球は球体なので、この正三角形の一つの角度は６０度を超えてしまいます。このように、われわれの正三角形の概念は、実は非常に曖昧です。そこで、点と線の数と結びつき方だけで、図形を分類して性質や特徴について調べようという考え方を発展させていったものが位相幾何学というものなのです。

参考；http://ja.m.wikipedia.org/wiki/グラフ理論

サーキットというグラフ その1

ここからは論理式をグラフとして扱う方法についてしばらく述べます。まじめに、やります。
　
さて、まず、グラフということについて簡単な説明をしましょう。
　
数学には、点と点をつないでその構造を扱う分野があり、かなり大きな一分野として確立されています。それをグラフ理論という呼び方をするわけですが、グラフというのは 、この点と点を線でつないだもの、と考えて下さい。そして、もう少し学問らしくしかめっ面をしながら格好を付けて、グラフの点のことを、「頂点」もしくは「接点」あるいは英語で「ノード（node）」という言い方をし、頂点同士をつなぐ線のことを「辺」もしくは「枝」あるいは英語では「エッジ（edge）」、「アーク（arc）」、「リンク（link）」などと呼びます。
　
呼び方がたくさんあるのは、数学にもいろいろな分野があり、また、広く、コンピュータ科学やその他の工学などにも応用、利用されているため、それぞれの専門分野に適した呼び名がされています。このブログでは、点を「接点」もしくは「ノード」、線を「枝」もしくは「エッジ」と呼ぶことにします。理由は、単に、私がそれに慣れているから、です。ちなみに、一般的な数学での標準的な呼び方は、「頂点」と「辺」のようです。だいたいそう書いてあります。
　
さて、グラフには、枝に向きがあるかないかで、大きく二つに分けることができます。枝に向きがある物を有方向グラフと言い、無グラフを無方向グラフと言います。はい、退屈ですね。良く分かります。しばらく退屈ですから寝てても良いですよ。ええ、私も眠たいですし。
　
では、ここからしばらくは、有方向グラフについて、いろいろな専門用語の定義です。まず、ノードv1からノードv2を結ぶ有方向の枝のことを、

　

　
という書き方をします。このほかの専門用語の解説です。
　
・サイクル（cycle）のあるグラフ
いくつかのノードを一周回るような枝のつなぎ方になっている場合をサイクルがあると言います
　
・無サイクル（acycle）グラフ
　サイクルがないようなグラフを無サイクル（acycle）なグラフと言います
　
・インデグリー（in degree）とアウトデグリー(out degree)
　無サイクルのグラフに限定した話になりますが、あるノードvに注目したとき、いくつの枝が入ってきているかをインデグリー（in degree）、いくつの枝が出て行っているかをアウトデグリー（out degree）と呼びます（下図参照）
　　

ここまで来てようやくサーキットというグラフについて説明となります。

サーキットという言葉には、もともとにはいろいろな意味があるようですが、ここではおそらく電子回路（それも、一つの伝線はオンかオフしかないデジタル回路）を指していると思われます。

つまり、サーキットというグラフは、デジタル回路を数学的に扱うためのグラフの一つと思えばいいわけです。サーキットの狼というマンガを知っている人は、おそらく私と同年代ですが、サーキット違いですのでロータス・ヨーロッパなどを想像しないように。
　
さて、そうなると、入力は当然0か1、あるいはT(True)かF(Flase)で考えることができます。すなわち、Bool代数の出番ということです。
　
Bool代数で使う専門用語を再掲しておくと、x1 ,…, xn をブール変数と呼び0（Ｆ）か1（Ｔ）のどちらかしかとりません。またこのブログでは、￢xiを便宜上ブール変数xiの否定と同等と扱い、ブール変数xiや￢xiと書かれたものを、リテラル、と呼んだりもするのでした。

では、いよいよサーキットというグラフについての定義をきちんとしましょう。基本的にやっているのは数学ですからね。定義は大事です。
　
【サーキットの定義】
　いま、ブール変数x1 , … , xnが与えられているとします。グラフは、無サイクルな有方向グラフであり、
　　
　　（１）すべてのノードのインデグリーは0、もしくは、2である
　　　　（１－１）インデグリー0のノードをインプットもしくはリーフと呼ぶ
　　　　　　　　　（一般に、入力であるブール変数x1 ,…, xn が相当する）
　　　　（１－２）インデグリー2のノードはゲート（gate）と呼ばれ
　　　　　　　　　∧（論理積）もしくは∨（論理和）が付加されている
　　（２）アウトデグリーの値は任意であるが、アウトデグリー0のノードが
　　　　　ただ一つだけあり、このノードのことをアウトプット(output)と呼ぶ
　
以上を満たすものをこれから、ブール変数x1 ,…, xn 上のブーリアン・サーキット（Boolean circuit）または、単にサーキットと呼ぶことにします。


少し話が長くなりました。もう少しだけ用語の定義がありますが、これは次回にしましょう。