サーキットというグラフ その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）または、単にサーキットと呼ぶことにします。


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