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$.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.