3.3.3 Binärer Baum im Hypercube

Zunächst wird ein Doppelwurzelbaum DWB(k) in den HC(k + 1) eingebettet.

Definition:

Ein Doppelwurzelbaum DWB(k) entsteht aus einem binären Baum B(k) , indem die Wurzel durch eine Kante mit zwei Knoten ersetzt wird.

Zwei B(1) und DWB(2)

Offenbar hat DWB(k) 2^{k + 1} Knoten.
Satz: DWB(k) ist Teilgraph des HC(k + 1) , Beweis durch Induktion.
Behauptung: DWB(k) ist Teilgraph des HC(k + 1) , und die drei Doppelwurzelkanten verlaufen in verschiedenen Dimensionen.
Verankerung: Bild 3.2 zeigt, wie der DWB(2) in den HC(3) eingebettet wird.

DWB(2) eingebettet in HC(3) (Doppelwurzelkanten fett)

Induktionsschritt: Sei bis k bewiesen. Durch Vertauschen von Bitpositionen bzw. Invertieren von Bitpositionen in allen Hypercubeadressen läßt sich erreichen, daß zwei DWB(k) im HC(k + 2) mit der in Bild 3.3 gewählten Numerierung eingebettet sind. Wie in Bild 3.4 zu sehen, lassen sich beide DWBe der Dimension k zu einem DWB(k + 1) zusammenfügen, wobei die drei Doppelwurzelkanten in verschiedenen Dimensionen verlaufen.

Gewählte Adressen für zwei DWB(k)

Zusammenfügen zweier DWB(k) zu einem DWB(k + 1)

Da ein binärer Baum B(k) aus DWB(k) durch Verschmelzen beider Wurzelknoten entsteht, folgt:

Korollar:

Ein binärer Baum B(k) läßt sich mit Kantenstreckung 2 (an einer einzigen Kante) in den HC(k + 1) einbetten.