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

このQ&Aのポイント
  • 距離の計算方法について解説
  • 問題の解法と正答について
  • 次元数による解法の考察
回答を見る
  • ベストアンサー

情報工学(ハードウェア) 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です。

質問者が選んだベストアンサー

  • ベストアンサー
  • myuki1232
  • ベストアンサー率57% (97/170)
回答No.1

対称性から、ある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) 任意のノードとの距離を求める方法がわかったので、後は単純な組み合わせの問題。

whyathome
質問者

お礼

なるほど、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) ですね。

関連するQ&A

  • 超立方体の経路の本数について

    超立方体の直径と同じ長さの経路は何本あるのでしょうか。 例えば3次元の超立方体の直径は3ですが、この長さ3の経路は4本ですか? 距離行列を書いたら3が8回出てきましたが…。 これは往復する分も含めるのでしょうか? n次元の長さnの経路は何本あるのか教えてください。 (2^n)/2ですか? ここの部分の回答が普通にスルーされて、すっきりしないので教えてください。

  • 数学の問題で困っています

    解ける問題だけでいいので、解いてください。 (1)一辺がacmの正方形の対角線の長さを求めなさい。 (2)高さが2√3cmの正三角形の一辺の長さを求めなさい。 (3)2点A(-1、3)、B(1、5)の間の距離を求めなさい。 (4)一辺が6cm立方体の対角線の長さを求めなさい。

  • 中学生の数学 証明問題

    中学生の問題ですが、解けません。どうぞご指導ください。問題 正方形ABCDにおいて2つの対角線の交点をEとする。辺CD上に2点C,Dと異なる点Fをとり、線分BFと線分ACとの交点をGとする。点Aから線分BFに垂線AHを引き、線分AHと線分BDとの交点をIとする。Q1 AI=BGであることを△AIEと△BGEが合同であることを証明して示しなさい。Q2 BH=2Cm HG=3Cm であるとき正方形の面積を求めなさい。 Q1は解けました。Q2が解けません。答えは40cm2ですが、解き方がわかりません。 よろしくお願いします。

  • 数学A二項定理

    Nを自然数として、xy平面上の点A(n,n)と原点Oを結ぶ線分を対角線とする正方形の周上または内部に、座標が整数であるような異なる2点P,Qをとるとき、次の問いに答えよ。(1)線分PQのとり方は何通りあるか。(2)線分PQが座標軸上にあるか、または座標軸に平行となるとり方は何通りあるか。(3)線分PQの長さが(ルート2)となるようなとり方は何通りあるか。(4)線分PQが対角線OAと共有点をもつようなとり方は何通りあるか。 答え;(1)(n+1)^2C2=n(n+1)^2(n+2) /2とおり  (2)2×n+1C2×(n+1)=n(n+1)^2とおり(3)2n^2とおり (4)n(n+1)(n+2)(n+3)/4とおり

  • 立方体を50mm標準レンズで見ると

      a..____b  ./   ./| A| ̄ ̄ ̄|B |  |     | .|c  |___|/ D     C 上図のような立方体があります。(dは隠れてます) 手前の正方形ABCDを正面から50mmレンズ(35mmフィルム換算)で見ると、 奥の正方形abcdの一辺は、正方形ABCDの一辺と比べてどれくらいの長さになるのでしょうか。 また、立方体を手前に置いた場合と奥に置いた場合でabcdとABCDの辺の比率に違いは出るのでしょうか。

  • 数学の問題

    縦91cm,横7cmの長方形に,1辺1cmの正方形を並べて,四隅をA,B,C,Dとする。直線ACが内部を通る正方形の数を求めなさい。直線ACは対角線です。 この問題って,どうやって解くのでしょうか。 答えは126個となっていますが,そう考えても132個になってしまいます。 なぜ126個なんでしょうか。

  • 3次元空間内での線分の交差判定について

    はじめまして。 3D関係のプログラムを組む上で、線分同士の判定を行う必要があるのですが 数学の知識が乏しく困っています。 3次元空間内の線分ABとCDが交差しているか判定し、 交差していればその交点を求めたいのです。 2次元の場合はできたのですが、3次元になるとどうやって計算すればよいのか わかりません。(交差以外に、ねじれの位置関係があるんですよね?) どなたか教えていただけると助かります。

  • 線分の交点の保持

    いつもお世話になってます。 2つ以上の線分が2次元上にあって、線分が交差した場合それぞれの交点を保ちながらも移動し、交点で回転しながら他の線分とも衝突判定を行う、というアルゴリズムを考えているのですがなかなかうまくいかず悩んでいます。 最終的にはたくさんの線分がくっついて、くねくねしながら移動するようなイメージです。 速度を同じにして、交点を軸に回転させてみたのですが、3本目の線分が交差したときうまくいかなくなってしまいました・・。 ぜひ皆さんの力を貸してください。よろしくお願いします。

  • 集合の要素の数の問題

    集合の要素の数の問題なのですが 生徒50人がA、B、C、D の問題を解いたところ Aの正答者は34人、Bの正答者は46人、Cの正答者は35人、Dの正答者は43人であった。 このとき、4題すべてが正解の生徒は最小の場合で何人いるか。 という問題です。 考え方がまったく分からず困っています。 どなたか解き方をわかりやすく解説していただけないでしょうか。

  • グラフの性質の問題について

    以下の問題、よろしくお願いします。 点の集合と点同士とを結ぶ辺の集合とからなる図形をグラフと呼びます。以下では立方体の頂点と辺からなるグラフを一般化して出来るグラフの性質を考察します。正方形は2次元の立方体なので2-cubeと呼ばれます。立方体は3-cubeです。数学では次元の低い方にも一般化を行います。 2点と2点を結ぶ直線からなるグラフは1-cubeです。n-cubeはn次元ユークリッド空間の超立方体の頂点と辺とからなるグラフです。nーcubeに関して以下の問に答えなさい。 問1 全ての辺の長さを1とします。ある点を1度だけ通過して点と点をつなぐ辺を辿り、異なる2点を結ぶ経路をパスと呼びます。あるグラフの上で、任意の2点x,yを結ぶパスp(x,y)の中でその長さ[p(x,y)] の最小値[p(x,y)]を点x,yの距離と呼びます。グラフ上で[p(x,y)]の最大値のグラフを直径と呼びます。n-cubeの直径をnの式で表しなさい。 問2 点の位置や辺の長さを自在に変えて曲線も許すとき、辺が交わらないように平面に作図可能なグラフを平面グラフと呼びます。2-cube、3-cubeは平面グラフですが、4-cubeはそうではありません。平面に描けないグラフを平面に描ける幾つかの部分に分解することができます。このとき、分解の最小数をグラフの厚さと呼びます。n-cubeの厚さをnの式で表しなさい。