07/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個のときも要がある。