発展途上国で町と町を結ぶ道路建設の仕事を任されたと想像してほしい。引き受けた時点では道路は１本もなく，ただ５０の町が孤立した状態で地図全体に点在している。これらの町を連結するのが仕事なのだが，ことはそう簡単ではない。いくつかの制約にも直面している。まず，たとえ場所を正確に指定して道路の建設を要求しても，およそ無能な道路局は無視するばかりで，どこか別のところ，行き当たりばったりで選んだ２つの町のあいだに道路を造ってしまうかもしれない。要求すれば道路は建設されるのだが，どこにできるかはいっさいわからないのだ。
さらにわるいことに，この国は資金にきわめて乏しく，そのため建設する道路の本数は可能なかぎり少なくしなければならない。したがって問題はこうなる。最低，何本の道路があれば十分か？財源の制約がなければ，２つの町がすべてつながるまで道路の建設をつづけるよう道路局に命じることもできるだろう。その場合，５０の町すべてが他の４９の町と道でつながるためには，１２２５本の道路が必要になる。だが，どの２つの町であろうと，道から１度もはずれることなくほぼ確実に車で行けるようにするには，最低で何本の道路を造ればいいのだろうか？
これは，グラフ理論ではもっともよく知られた問題の１つである。もちろん，必ずしも町と道路の必要はない。家と電話回線，人と人との交友関係，ひもでランダムにつながれた犬の群れなど，他にもいろいろな形で表すことができる。基本的な問題はどれも同じだが，問題を解くのはけっして簡単ではない。だから答えがわからなくても気にする必要はない。実際，この難問を解くにはポール・エルデシュ並の才能が求められるのだ。ちなみに，エルデシュが解いたのは１９５９年のことで，大多数の町を確実に結ぶには，９８本の道路をランダムに配備すれば十分なことがわかったのである。９８本はかなりの本数のように思えるかもしれないが，５０の町のあいだに建設可能な１２２５本の道にリンクを張るのは，思ったほど非効率的ではないのだ。
マーク・ブキャナン 阪本芳久（訳） (2005). 複雑な世界，単純な法則：ネットワーク科学の最前線 草思社 pp.50-51
（Buchanan, M. (2002). Nexus: Small Worlds and the Groundbreaking Science of Networks. New York: W. W. Norton & Company.）
PR
