Butterfly graph

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

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

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

[math]\displaystyle{ \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]\displaystyle{ \,q+1\pmod {n} }[/math] of [math]\displaystyle{ {\mathcal B}(n) }[/math], for [math]\displaystyle{ \,\gamma = 0, 1 }[/math].

Литература

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