2.2.6 Der Hypercube

Ein $d$-dimensionaler Hypercube hat genau $P = 2^d$ Knoten.

Rekursiver Aufbau

• Platzierung der Knoten nach dem Gray-Code
• Ein Hypercube der Dimension $d$ ergibt sich durch die entsprechende Verbindung zweier Hypercubes der Dimension $d-1$.
• Im Hypercube benachbarte Knoten unterscheiden sich in genau einem Bit ihrer Knotennummern in Binärdarstellung. Die Position des Bits legt eindeutig die Nummer des die beiden Knoten verbindenden Links fest (z.B. sind Knoten $5=LOL$ und $4=L00$ über Link $1$ im 3-dimensionalen Hypercube miteinander verbunden).
• Die Links mit gleicher Linknummer (=Bitposition) teilen den $d$-dimensionalen Hypercube in 2 $(d-1)$-dimensionale Hypercubes. Je nachdem ob die zum Link gehörende Bitposition gesetzt ist, ordnen sich die Knoten den beiden Subcubes zu. So teilt z.B. Link 2 den 3-dimensionalen Hypercube in Abbildung 2.6 in die Subcubes  $\{0,1,4,5\}$ und  $\{2,3,6,7\}$.

  

Abbildung 2.6: Hypercube $d=0,\ldots ,3$

• $d$ Links pro Knoten
• Max. Weglänge: $d = \log_{2} P$
• Kürzester Weg im Hypercube zwischen den Knoten $p$ und $q$ ergibt sich aus XOR($p$,$q$) , worin die gesetzten Bits den Linknummern entsprechen, welche die Verbindung bilden.
  
  Bsp.: $p = 1 = 00L$, $q = 7 = LLL$ $\Longrightarrow$ XOR($1$,$7$) $= LL0$
  Der Weg in obigem Beispiel ist in einen 2-dimensionalen Subcube des Hypercubes eingebettet.
• Hardware: nCube

Die Topologien Ring, Torus und Tree (2.2.2 - 2.2.5) sind im Hypercube eingebettet.
So läßt sich ein Ring mit $P = 2^d$ Knoten ähnlich rekursiv wie der Hypercube definieren und somit in diesen einbetten:

 

Abbildung 2.7: Einbettung des Ringes im 3D-Hypercube

Aufgabe :

Betten Sie einen $2^k \times 2^{\ell}$-Torus in einen ($k+{\ell}$)-dimensionalen Hypercube ein.  




Aufgabe :

Zeigen Sie anhand des Hypercube-3, daß der optimale Baum (Punkt 2.2.5) mit der Wurzel im Knoten $000$ im Hypercube eingebettet ist. Wieviele verschiedene Einbettungsmöglichkeiten gibt es ?  




Aufgabe :

Geben Sie eine Einbettung des optimalen Baums mit der Wurzel im Knoten $L0L$ für den Hypercube-3 an.  




Aufgabe :

Bilden Sie die Knoten (über ihre Nummern) der beiden Bäume aus den beiden vorangegangenen Aufgaben aufeinander ab.