衛星InterCom研究所


研究所の概要

衛星InterCom研究所へようこそ。この研究所では緊急事態にそなえて、どんな連絡網が一番効率がよいかということを追求、研究を おこなっている。あまり起こってほしくないことであるが、われ等がグラフ惑星に巨大隕石の衝突が確実となった場合、支配者和田教授は 全員に避難命令を発令することになっている。がしかし、その方法については規定されていないのが現実である。 そこで、その研究について簡単に説明しよう。

このようなときにどんな緊急連絡網が一番効率がよいのだろうか?
このグラフ惑星の人口は5人。この5人だとどのようにすると一番効率がよいのだろうか?
まず最初にこんな風な連絡網はどうだろう。
惑星の住人を簡単のためにそれぞれA,B,C,D,Eとすると・・・
A→B→C→D→E
この方法だと一回の電話にかかる時間を1とすると4時間かかっている。
また全員が一回しか電話をかけていないからもっと時間をへらせるんじゃないか?
たとえばAなんて時刻2からはずっと3時間何もしていない。
だから全員がいつも誰かに電話をかけている状態にすればいいから・・・
時刻1: A→B
時刻2: A→C, B→D
時刻3: A→E
こうするとさっきかかっていた時間から1減らせることができた。

でもいったいどこまで減らせるんだろう?このかかる時間は。
最初は誰か一人だけが連絡する情報をもっている。これを時刻0とすると、
時刻1には情報を持っている人は2人。そして時刻2には4人。
なるほど。

時刻Tで情報を持っている人がX人だったら
時刻(T+1)では2X人にできる。

だから、Y人の星で緊急連絡網を作成する場合、最初は情報を持っているのが一人で
時間が進むごとに情報を持っている人の数を倍倍にできるから、

一番効率よく電話をかけたとしても
log Y(底が2の対数)の切り上げの時間
は絶対必要!

ということになる。 じゃぁ、さっきグラフ惑星用につくって3時間かかる連絡網は・・・
人口が5人だから、さっきの事実からlog 5の切り上げ、つまり3時間は絶対にかかるってことになるね。
ということは、あの連絡網が最適ということになる!

この場合は5人だったので全員の電話番号を知っているとしてよいが、
人数が多い惑星になると話しはちがってくるだろう。
たとえば、和田・犬塚星系においても約30人の人が住んでいると、
全員が全員の電話番号を知っているとはいえないからだ。
このとき、人を頂点、電話番号を知っているもの同士を辺であらわすとそれはグラフになる。
(グラフとは点とそれらをつなぐ線からなる図形のこと)
先ほどのグラフ惑星の例では全員が全員の電話番号を知っている場合、
グラフでは完全グラフと呼ばれるものである。
グラフが完全グラフでない場合さっきの強力な事実が揺らいでしまう。

時刻Tで情報を持っている人がX人だったら
時刻(T+1)では2X人にできる

ではなく、

時刻Tで情報を持っている人がX人だったら
時刻(T+1)では
増やせるだけ増やしたとしても高々2X人である。

もう、情報を知っている人の数を倍倍にはできないのだ!

そうなるとどうやったらいいのだろうか?これはこの研究所の主な研究テーマのひとつだ。
住人の間の電話番号の交換状況は絶対グラフにできるので、以降はグラフで考えればよい。
そこで、われわれの研究所では以下のような問題について研究・考察を行っている。 といった問題を研究している。現在、これらの問題は非常に困難で他の衛星の責任者などとも共同で研究を進めているが
手を焼いているのが現状である。ぜひとも興味のある諸君の参加を待っている!
何か聞きたいこと、興味がわいたのでぜひ話してみたい等在る肩は衛星InterCom研究所を尋ねてほしい!
もう少し技術的な説明はこの星の研究所責任者である 大村伸吾のページへ。

衛星InterComの位置
20号館4階401室内 大村 伸吾 shingo@phaser.elcom.nitech.ac.jp

グラフ惑星のページに戻る