面白い問題おしえて〜な 十三問目
■ このスレッドは過去ログ倉庫に格納されています
0181132人目の素数さん
2007/10/05(金) 04:38:29互いに離れたところにいくつかの通信基地がある。
これらの基地の間には通信ケーブルが張り巡らされており、
どの二つの基地もちょうど一本のケーブルで結ばれている。
ところがこのケーブルは一方通行でしか情報を送れない。
つまり、二つの基地の間で、どちらかの基地は他方へ情報を送信できるが、逆方向へは直接送信はできない
このような通信基地たちとケーブルによって構成された通信網を考える。
さて、Aを通信基地のひとつとする。
もし以下が成り立つならば、このようなAを通信網の要と呼ぶ
「任意の基地B(A自身は除く)に対して�@または�Aが成り立つ
�@)AとBの間のケーブルはAが送信側でBが受信側である
(これをA→Bと書くことにする)
�A)ある基地CがあってA→C→Bである 」
つまり、Aが要であるとはAは自分以外のどの基地へも高々2ステップで情報を送信できる事を意味する。
問題:
どんな通信網も必ず少なくとも一つ要を持つことを示せ
■ このスレッドは過去ログ倉庫に格納されています