Butterfly graph: различия между версиями

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

Let <math>n</math> be a positive integer. The <math>n</math>-level '''butterfly graph''' <math>{\mathcal B}(n)</math>

is a digraph whose vertices comprise the set <math>V_{n} = Z_{n} \times

Z_{2}^{n}</math>. The subset <math>V_{n}^{q} = \{q\} \times Z_{2}^{n}</math> of <math>V_{n}</math>

(<math>0 \leq q < n</math>) comprises the <math>q^{th}</math> level of <math>{\mathcal B}(n)</math>.

The arcs of <math>{\mathcal B}(n)</math> form directed butterflies (or, copies of the

directed complete bipartite graph <math>K_{2,2}</math>) between consecutive

levels of vertices, with wraparound in the sense that level <math>0</math> is

identified with level <math>n</math>. Each butterfly connects each vertex

on level <math>q</math> of <math>{\mathcal B}(n)</math> (<math>q \in Z_{n}</math>; <math>\alpha</math> and each

<math>\beta_{i}</math> in <math>Z_{2}</math>) to both vertices

<math>\langle q+1\pmod {n}, \beta_{0}\beta_{!} \cdots \beta_{q-1}\gamma

\beta_{q+1}\cdots \beta_{n-1}\rangle</math>

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