Butterfly graph

Butterfly graph --- граф-бабочка.

Let $n$ be a positive integer. The $n$-level butterfly graph ${\mathcal B}(n)$ is a digraph whose vertices comprise the set $V_{n} = Z_{n} \times Z_{2}^{n}$. The subset $V_{n}^{q} = \{q\} \times Z_{2}^{n}$ of $V_{n}$ ($0 \leq q < n$) comprises the $q^{th}$ level of ${\mathcal B}(n)$.

The arcs of ${\mathcal B}(n)$ form directed butterflies (or, copies of the directed complete bipartite graph $K_{2,2}$) between consecutive levels of vertices, with wraparound in the sense that level $0$ is identified with level $n$. Each butterfly connects each vertex $\langle q,\beta_{0}\beta_{1} \cdots\beta_{q-1} \alpha \beta_{q+1}\cdots \beta_{n-1}\rangle$ on level $q$ of ${\mathcal B}(n)$ ($q \in Z_{n}$; $\alpha$ and each $\beta_{i}$ in $Z_{2}$) to both vertices

$\langle q+1\pmod {n}, \beta_{0}\beta_{!} \cdots \beta_{q-1}\gamma \beta_{q+1}\cdots \beta_{n-1}\rangle$

on level $q+1\pmod {n}$ of ${\mathcal B}(n)$, for $\gamma = 0, 1$.