3.2.7 Hypercube

Ein Hypercube der Dimension k (HC(k)) besteht aus p = 2^k Knoten. Jeder Knoten hat k Nachbarn, deren Adresse an genau einem Bit differieren.

K₁ :	ja
K₂ :	k
K₃ :	korrigiere alle zwischen Start- und Zieladresse differierenden Bits durch Benutzung der zuständigen Links
K₄ :	k
K₅ :	ja, für k $\geq$ 2 . Induktion über k : Hypercube der Dimension 2 hat Hamiltonkreis. Hypercube der Dimension k setzt sich zusammen aus 2 Hypercubes der Dimension k - 1 . Verbinde deren Hamiltonwege.

Verbinden zweier Hypercube-Hamiltonkreise

Hypercubes der Dimension 0, 1, 2, 3, 4.

Routing von Startadresse 0101 über 0111 und 0011 zu 1011.

Es gibt 2 Ansätze, den variablen Knotengrad des Hypercube auf eine Konstante zu drücken unter Beibehaltung der prinzipiellen Verbindungs- und Routing-Struktur: Beim Butterfly-Netzwerk existieren log p abgemagerte Kopien des Hypercube; bei den Cube Connected Cycles wird jeder Hypercubeknoten durch einen Ring mit log p Knoten ersetzt.

	Hypercubes der Dimension 0, 1, 2, 3, 4.
	Routing von Startadresse `0101` über `0111` und `0011` zu `1011`.