3.2.11 de Bruijn

Ein de Bruijn-Netzwerk der Dimension k ( dB(k) ) besteht aus p = 2^k Knoten. Von einem Knoten mit dem Binärmuster x₁x₂...x_k führt eine Shuffle-Kante zu dem Knoten mit Binärmuster x₂...x_kx₁ und eine Shuffle-Exchange-Kante zu dem Knoten mit Binärmuster x₂...x_k$\overline{x}_{1}^{}$ .

de Bruijn-Netzwerk der Dimension 3

K₁ : ja

K₂ : 4 (wenn Richtung ignoriert wird)

K₃ : Um von x nach y zu gelangen: Passe schrittweise die Bits von x den Bits von y an. Konstruiere jeweils im letzten Bit (durch Übernahme oder Invertierung des vordersten Bits) das nächste Bit der Zieladresse.

K₄ : k

K₅ : ja

Zum Nachweis der Hamiltonkreis-Eigenschaft benötigen wir die Definition des Kantengraphen: Sei $\mbox{G}$ = ($\mbox{V}$,$\mbox{E}$) ein gerichteter Graph. Der Kantengraph $\hat{G}$ von $\mbox{G}$ ist definiert als $\hat{G}$ = ($\mbox{E}$,$\hat{E}$) mit

Offenbar hat $\hat{G}$ so viele Knoten wie $\mbox{G}$ Kanten.

Beziehung zwischen Graph $\mbox{G}$ und Kantengraph $\hat{G}$

Beim de Bruijn-Graphen läßt sich die Kante von u nach v mit uv₀ eindeutig beschreiben. Somit gilt

u = u_{k - 1} u_{k - 2} u_{k - 3} ... u₀

v = u_{k - 2} u_{k - 3} ... u₀ v₀

w = u_{k - 3} ... u₀ v₀ w₀

e₁ = u_{k - 1} u_{k - 2} u_{k - 3} ... u₀ v₀

e₂ = u_{k - 2} u_{k - 3} ... u₀ v₀ w₀

Also entstehen in $\hat{E}$ genau die de Bruijn-Kanten, d.h., der Kantengraph von dB(k) ist der Graph dB(k + 1) .
Da der dB(k) einen Eulerkreis hat (denn jeder Knoten hat 2 Eingangs- und 2 Ausgangskanten), besitzt dB(k + 1) einen Hamiltonkreis.