Butterfly-Graphen

Ein $n$ dimensionaler Butterfly-Graph zur Basis 2 besteht aus $n$ Stufen und $2^n$ Knoten pro Stufe. Für die Stufen $t = 1, \dots, n$ ist ein Knoten $a = (a_{n-1}, \dots, a_0)_2$ mit den beiden Vorgängern $(a_{n-1}, \dots, a_{n-t+1}, 0, a_{n-t-1}, \dots, a_0)_2$ und
$(a_{n-1}, \dots, a_{n-t+1}, 1, a_{n-t-1}, \dots, a_0)_2$ verbunden (Abbildung ).