Butterfly graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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.