- 722 名前：デフォルトの名無しさん mailto:sage [2010/02/20(土) 01:29:14 ]
- >>721を書いてから半分にできることに気づいた
戦略：
・全部のページを同じ大きさのm個のグループに分ける
・グループ内のページは全て相互リンクする
・グループ内の(m-1)個のページにそれぞれ担当のグループを割り当て、
グループ間の担当のページ同士を相互リンクする
・任意の2ページ間は多くても
自グループの担当ページ→目標グループの担当ページ→目標ページ
の3クリックで移動できる
このとき、リンクの数が一番多いのはグループ間を繋ぐ担当のページで、
max(link(n)) = (グループ内の全結合） + （担当グループへのリンク） = N/m-1 + 1
最も効率が良くなるのは、グループ内の全てのページが他のグループの担当ページになるとき、
つまり N/m = m のときで、そのときm = √Nであって、 min(max(link(n))) = √N。
