Butterfly graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Butterfly graph''' --- граф-бабочка. Let <math>n</math> be a positive integer. The <math>n</math>-level '''butterfly graph''' <math>{\mathcal B}(n)</…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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> | ||
\ | on level <math> \,q+1\pmod {n} </math> of <math>{\mathcal B}(n)</math>, for <math> \,\gamma = 0, 1</math>. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 16:31, 23 октября 2018
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.