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

前回まで、簡単にグラフ理論にふれ、サーキットというグラフについて定義しました。今回はもう少しだけ詳しく説明し、そのほかの用語の解説の続きを行います。
　
ところで、ここまでこのブログではいろいろなアメリカのＩＴ企業との関連について（少し無理矢理）触れてきましたが、グラフ理論といえばグーグル。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)の値とするというのがあるのです。随分と面倒ですよね。