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

Материал из WikiGrapp
Перейти к:навигация, поиск
(Новая страница: «'''Butterfly graph''' --- граф-бабочка. Let <math>n</math> be a positive integer. The <math>n</math>-level '''butterfly graph''' <math>{\mathcal B}(n)</…»)
 
 
Строка 1: Строка 1:
'''Butterfly graph''' --- граф-бабочка.  
+
'''Butterfly graph''' — ''[[граф-бабочка]].''
  
Let <math>n</math> be a positive integer. The <math>n</math>-level '''butterfly graph''' <math>{\mathcal B}(n)</math>
+
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
+
is a [[digraph]] whose [[vertex|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>
+
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>.
+
(<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
+
The [[arc|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
+
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
+
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
+
identified with level <math>\,n</math>. Each butterfly connects each vertex
 
<math>\langle q,\beta_{0}\beta_{1} \cdots\beta_{q-1} \alpha
 
<math>\langle q,\beta_{0}\beta_{1} \cdots\beta_{q-1} \alpha
 
\beta_{q+1}\cdots \beta_{n-1}\rangle</math>
 
\beta_{q+1}\cdots \beta_{n-1}\rangle</math>
on level <math>q</math> of <math>{\mathcal B}(n)</math> (<math>q \in Z_{n}</math>; <math>\alpha</math> and each
+
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>\,\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
+
:::::<math>\langle q+1\pmod {n}, \beta_{0}\beta_{!} \cdots \beta_{q-1}\gamma \beta_{q+1}\cdots \beta_{n-1}\rangle</math>
  
\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>.
 +
 
 +
==Литература==
  
on level <math> q+1\pmod {n} </math> of <math>{\mathcal B}(n)</math>, for <math> \gamma = 0, 1</math>.
+
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия на 11:16, 24 апреля 2012

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.