Butterfly graph

Материал из WikiGrapp
Версия от 15:14, 24 февраля 2011; Glk (обсуждение | вклад) (Новая страница: «'''Butterfly graph''' --- граф-бабочка. Let <math>n</math> be a positive integer. The <math>n</math>-level '''butterfly graph''' <math>{\mathcal B}(n)</…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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.