- 721 名前：デフォルトの名無しさん mailto:sage [2010/02/20(土) 01:10:58 ]
- >>713
ページ数Nに対して 2√N くらいじゃないかね
戦略：
・全部のページを同じ大きさのm個のグループに分ける(各グループには N/m ページある）
・各グループにインデックスページを作り、
グループ内の他の全てのページと相互リンクする
・各グループのインデックスページを全て相互リンクする
・任意の2ページ間は多くても
自グループのインデックス→目標グループのインデックス→目標ページ
の3クリックで移動できる
一番リンクの数が多いのは各グループのインデックスページで、
max(link(n)) = (インデックス間の全結合) + (グループ内のリンク） ≒ m + N/m
これが最小になるのは m=√N のときで min(max(link(n))) ≒ 2√N
