- 183 名前:132人目の素数さん mailto:sage [2007/10/07(日) 04:03:50 ]
- >>181
N個の基地からなる通信網に要Aがあると仮定する。 Aから1ステップで到達できる基地をB={B1,B2,‥,Bm}とし、 残り全部をC={C1,C2,‥,Cn}とする。 仮定より、Cの基地は全て、あるBiから1ステップで到達できる。 ここに新たに基地Xを追加したとき、 ・A→XならAが要。 ・あるBiに対しBi→Xなら、A→Bi→Xとなるため、やはりAが要。 ・X→A、かつ全てのBiに対しX→Biのときは、任意のCjに対し あるBkがあってX→Bk→Cjとなるため、Xが要になる。 よって、N+1個のときも要がある。
|
![](http://yomi.mobi/qr.gif)
|