De Bruijn-Graphen

Ein $n$ dimensionaler de Bruijn-Graph zur Basis 2 besteht aus $2^n$ Knoten und $2^(n+1)$ Kanten. Jeder Knoten hat 2 ein- und 2 ausgehende Kanten. Bei der Beschreibung von Verbindungsnetzwerken werden de Bruijn-Graph iterativ verwendet. Ein Knoten $a = (a_{n-1}, \dots, a_0)_2$ ist mit seinen Vorgaengern $(0, a_{n-1}, \dots, a_1)_2$ und $(1, a_{n-1}, \dots, a_1)_2$ und seinen Nachfolgern $(a_{n-2}, \dots, a_1, 0)_2$ und $(a_{n-2}, \dots, a_1, 1)_2$ verbunden (Abbildung ).