- 181 名前：１３２人目の素数さん mailto:sage [2007/10/05(金) 04:38:29 ]
- 通信網の問題：
互いに離れたところにいくつかの通信基地がある。
これらの基地の間には通信ケーブルが張り巡らされており、
どの二つの基地もちょうど一本のケーブルで結ばれている。
ところがこのケーブルは一方通行でしか情報を送れない。
つまり、二つの基地の間で、どちらかの基地は他方へ情報を送信できるが、逆方向へは直接送信はできない
このような通信基地たちとケーブルによって構成された通信網を考える。
さて、Ａを通信基地のひとつとする。
もし以下が成り立つならば、このようなＡを通信網の要と呼ぶ
「任意の基地Ｂ(Ａ自身は除く)に対してⅰまたはⅱが成り立つ
ⅰ)ＡとＢの間のケーブルはＡが送信側でＢが受信側である
（これをＡ→Ｂと書くことにする）
ⅱ）ある基地ＣがあってＡ→Ｃ→Ｂである 」
つまり、Ａが要であるとはＡは自分以外のどの基地へも高々２ステップで情報を送信できる事を意味する。
問題：
どんな通信網も必ず少なくとも一つ要を持つことを示せ
