情報工学(ハードウェア) 2進ハイパーキューブ網

質問

添付画像の問題について解説をお願いします。

D=1の場合
線分をイメージして、平均距離は1
D=2の場合
正方形をイメージして、距離1となる経路の数は辺の数だから4
距離2となる経路の数は対角線の数だから2
よって平均距離は 1*4+2*2/6=4/3
D=3の場合
立方体をイメージして、距離1となる経路の数は12
距離2となる経路の数は、面上の対角線の数だから12
距離3となる経路の数は、面上以外の対角線の数だから4
よって平均距離は 1*12+2*12+3*4/28=12/7

と考えられると思ったのですが、4次元、5次元の場合について行き詰まってしまいました。

そもそも上記の考え方は正しいでしょうか？
また、正答は規則性を用いることで、導けますか？

よろしくお願いします。
ちなみに正答は肢4です。

回答No.1

myuki1232 · ベストアンサー

対称性から、ある1つのノードと他の任意のノードとの距離を求める方法がわかれば解ける。

まず、N次元の任意のノードを表現する方法を考えると、すべてのノードはハイパーキューブの頂点にあるため、N次のベクトル (a_1, a_2, ..., a_N) と表せる。ただし、a_n = 0, 1。
次に、任意のノードに繋がっているノード（距離が1のノード）を求める方法を考える。
例えば、要素すべてが 0 のノード (0, 0, ..., 0) （以下、原点ノードと呼ぶ）と繋がっているノードは、(1, 0, ..., 0), (0, 1, ..., 0), ..., (0, 0, ..., 1) のN個である。
ここで、対称性から、あるノードと繋がっているノードは、ベクトルの要素の1つが 0 と 1 が反転したものであるという法則があることがわかる。
さらに、ノード間の距離は最短距離を使うため、原点ノードとその他の任意のノードとの距離は、そのノードの要素の中の 1 の数の合計である。（例えば、原点ノードと (1, 0, 0, 1, 0) との距離は 2）

任意のノードとの距離を求める方法がわかったので、後は単純な組み合わせの問題。

お礼

なるほど、5次元の平均距離を求める場合は、
(5C1+2*5C2+3*5C3+4*5C4+5*5C5)/(5C1+5C2+5C3+5C4+5C5)
で求められますね！
とすると、n次元の平均距離は
Σ[k=1~n](k*nCk)/Σ[k=1~n](nCk)
ですね。