K1 : | ja |
K2 : | k |
K3 : | korrigiere alle zwischen Start- und Zieladresse differierenden Bits durch Benutzung der zuständigen Links |
K4 : | k |
K5 : | ja, für k 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. |
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.