今日のお勉強

グラフって何?

で、グラフっていうのは、まあいろんな言い方があるんですけど、有限集合、これを多くの場合Vと書きますけど、有限集合V上の2項関係の有無を表すものです。
例えば、仕事が、例えばv1からv4まであったとして、同時にできない仕事の対っていうのを考えます。対っていうのはpairですね。
2項関係ですから、4つ全体で関係が出てくるんじゃなくて、2つの間で関係があると言うんですね。v1,v2,v3,v4というのをこういう風に点で表すわけです。

[グラフ-仕事]

まあ、たとえばこういうふうに、対を枝で表すわけですね。
今の場合はv1とv2は同時には仕事ができない。v1とv3もやっぱり同時には仕事ができない。v1とv4も同時にはできない。でもv2とv4は同時に仕事していいよ。v3とv4も同時に仕事していいよ。
例えばこういうことで、今の場合は同時にできない仕事のpairっていうのを、2つの間でできないんだったら、こう、関係で表すわけですね。
例えばこういう時に何ができるかっていうと、全然枝が無ければですね、すべての仕事が同時にできるわけですから、例えば、並列にほんとに仕事ができるんだったらば、一斉に仕事をボッと始めてしまっていいわけです。でも今の場合コンフリクトがあって、例えばv1とv2、v1とv3が同時にやっちゃいけないわけですよね。
少なくとも枝が1本あるわけですから、v1とv4は同時にはできないんだから、まずどちらかを最初にやって、終った後に残りをやらなければならない。
例えば今、仮定として、仕事が1単位時間で終るとしましょう。そうした時に、今、枝があるから、少なくとも2つ同時にはできないやつがあるから、2単位時間が必要なことはいいんですけれども、今、ここに3角形がありますよね。ということはこれは3単位時間必要ですよね。
例えば、これで、各仕事が単位時間でできるとします。

[有効でないスケジュール] [有効なスケジュール]

タイムスロット1というのがあって、ここで、プロセッサ1台で、仕事v1をしてv2をしてv3をしてv4をしてっていうことは、これはできないわけですね。
えっと、これ、何を言いたいかっていうと、0時間から始まって、並列プロセッサでもいいですし、同じ1つのプロセッサで仕事をしていると思ってもしてもいいんですけれども、まあ、ここのグラフで表したのが、v1とv2は同時に仕事ができないってことですから、これはコンフリクトがあるわけですね。同時にできないわけです。これは、有効でないスケジュールになってるわけですね。
有効なスケジュールはどのようになるかっていうと、明らかにこの場合簡単で、v1 を一番最初にやるっていうのは良くって、v2をやる時に一緒にv4もできるわけです。v2とv4は同時に仕事ができることになってるわけですね。
で、さっきのは有効でなかったんですが、これは有効なスケジュールになっています。
もちろん今の場合、v4をv3と一緒にやってもいいのですけれども、まあいろいろなクライテリア(判断の基準)があるわけです。で、これはグラフっていうもの、すなわち有限集合があって、その間の2項関係の有る無しを枝で表現する、要するに関係があれば枝で2つの点を結んで、なければ枝で結ばないということで表現された構造に対して、例えば、こういうスケジューリングの問題が対応するってわけですね。

実は、このスケジュールっていうのは、基礎論(現在の「情報数学」)でやったカラーリングの話に対応すると。
基礎論では、地図の4色塗り分けってのをお話だけして、実際に理論的に目指したことは何だったかっていうと、6色で塗れることは納得できるようにしましょうというのを目指して頑張って喋ったつもりなんですけれども、ちょっと最後、きつくなって申し訳ありませんでしたが。

こういう地図があったら、4色で塗ってみましょうね。 [4色地図]
例えば、ここは赤で塗ります。これ、地図ですから、隣接する国は必ず違う色で塗らなければいけないわけですね。 [4色地図1]
ここ黄色で塗ります。 [4色地図2]
ここも黄色で塗ります。 [4色地図3]
ここは黄色も赤もおけないから、青で塗りますよね。 [4色地図4]
ここは例えば、赤で塗るんですけれども、 [4色地図5]
ここはやっぱり違う色で塗らなければならないんですね。こういう地図を塗り分ける時、4色必要なわけですね。 [4色地図final]
ちなみに、これ、ごめんなさい、4色で塗り分けるやり方をやって、4色必要かどうかは納得できないですが、まあ、4色必要な場合は簡単に作れるはずで、といっても、即興で例をつくって、4色必要でなかったりするわけですが。

まあ、実はこういうスケジュールの話をすると、一緒のカラーリングの話になるわけです。今の場合、国が隣接しているというのが2項関係だったわけですね。
で、それを、同時に仕事ができないというふうに考えたらスケジューリングなんかの話にも対応しているわけです。

こういうことで、基本的にはグラフっていうのはこういう風に定義されているんですけれども、対象構造に関して2項関係の有る無しを枝の有る無しで表現しておいて、そういうものに関して考えているのがグラフなわけです。

で、有限集合を点集合として考えて、それがVで、どうしてVだったかっていうと、このあたり復習の部分になると思いますが、vertexと呼ばれるからですね。
で、枝集合をedgeのEで表します。だから、Vというのが、v1,v2,・・・,vnとなっているものの有限集合で、Eというのはe1,e2,・・・,em、よく 枝の方のインデックスにはmを用いますけれども、i番目の枝というものは、vjとvkのpair{vj,vk} として表されます。
これは集合の記法ですから、{vj, vk}と書いたものと{vk,vj}と書いたものは一緒なわけですよね、一方、(vj,vk)と書いたものだと順番がついているわけですよね。だから、これからは両方のノーテーションを使います。
で、基本的には、どちらかというと(vj,vk)のノーテーションを使います。
[無向枝]

[有向枝]

で、基本的には、どちらかというと(vj,vk)のノーテーションを使います。
ただ、この場合も、無向の場合(向きがない場合)と、有向の場合、どちらにも使います。
有向の場合は、必ず、順番に意味があって、(vj,vk)がvjからvkへの枝というふうにこの場合は考えるわけですね。だから、無向か有向かをその場その場のコンテクストで明らかにしておいて、このノーテーションは両方で使います。

そろそろ、こういう話をしていると、グラフの一番最初からですねぇ、パスの定義とかもういっぺんやんないといけないので、やるんですが、退屈なので、まず先に、今日の目標の話をします。


Prev Next

 

〔トップページへ〕 〔離散数学の仮想講義のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 7 May, 1999