Circulant graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Circulant graph''' --- циркулянтный граф. '''1.''' Let <math>p</math> be a positive integer and <math>S</math> be a subset of <math>\{1,2, \ldot…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Circulant graph''' | '''Circulant graph''' — ''[[циркулянтный граф]].'' | ||
'''1.''' Let <math>p</math> be a positive integer and <math>S</math> be a subset of <math>\{1,2, | '''1.''' Let <math>\,p</math> be a positive integer and <math>\,S</math> be a subset of <math>\{1,2, \ldots, p-1\}</math>, such that <math>i \in S</math> implies <math>p-i \in S</math>. A '''circulant graph''' <math>\,G(p,S)</math> has [[vertex|vertices]] <math>0,1, \ldots, p-1</math> and two vertices <math>\,i</math> and <math>\,j</math> are ''[[adjacent vertices|adjacent]]'' if and only if <math>i - j \in S</math>, where subtraction is carried out modulo <math>\,p</math>. The [[adjacency matrix]] of a circulant graph is a ''symmetric circulant''. | ||
\ldots, p-1\}</math>, such that <math>i \in S</math> implies <math>p-i \in S</math>. A '''circulant graph''' <math>G(p,S)</math> has vertices <math>0,1, \ldots, p-1</math> and two vertices <math>i</math> and <math>j</math> | |||
are ''adjacent'' if and only if <math>i - j \in S</math>, where subtraction is | |||
carried out modulo <math>p</math>. The adjacency matrix of a circulant graph is a | |||
''symmetric circulant''. | |||
'''2.''' (A circulant graph <math>G(n,d)</math>). The '''circulant graph''' <math>G(n,d)</math> with <math>d \geq 2</math> | '''2.''' (A circulant graph <math>\,G(n,d)</math>). The '''circulant graph''' <math>\,G(n,d)</math> with <math>d \geq 2</math> is defined as follows. The vertex set is <math>V = \{0,1,2, \ldots, n-1\}</math>, and the [[edge]] set is <math>E = \{(u,v)| \exists i, 0 \leq i \leq \lceil | ||
is defined as follows. The vertex set is <math>V = \{0,1,2, \ldots, n-1\}</math>, | |||
and the edge set is <math>E = \{(u,v)| \exists i, 0 \leq i \leq \lceil | |||
\log_{d}(n)\rceil - 1</math>, such that <math>u + d^{i} \equiv v\pmod{n}\}</math>. | \log_{d}(n)\rceil - 1</math>, such that <math>u + d^{i} \equiv v\pmod{n}\}</math>. | ||
'''3.''' (A circulant graph <math>G(cd^{m},d)</math>). The '''circulant graph''' <math>G(cd^{m},d)</math> has | '''3.''' (A circulant graph <math>\,G(cd^{m},d)</math>). The '''circulant graph''' <math>\,G(cd^{m},d)</math> has <math>\,cd^{m}</math> vertices <math>\,(0 < c < d)</math>. <math>V = \{0, \ldots, cd^{m} - 1\}</math> is the set of vertices, and <math>E = \{(v,w), v, w \in V/\exists i, 0 \leq i \leq \lceil \log_{d}cd^{m}\rceil - 1, v \pm d^{i} \equiv w\pmod{cd^{m}}\}.</math> An edge between <math>v</math> and <math>w = v \pm d^{i}</math> will have the label <math>d^{i}</math>. It is easy to see that <math>\,G(cd^{m},d)</math> is a ''[[Cayley graph]]'' defined on an abelian group. | ||
<math>cd^{m}</math> vertices <math>(0 < c < d)</math>. <math>V = \{0, \ldots, cd^{m} - 1\}</math> is | |||
the set of vertices, and <math>E = \{(v,w), v, w \in V/\exists i, 0 \leq i | ==Литература== | ||
\leq \lceil \log_{d}cd^{m}\rceil - 1, v \pm d^{i} \equiv | |||
w\pmod{cd^{m}}\}.</math> An edge between <math>v</math> and <math>w = v \pm d^{i}</math> will have | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
the label <math>d^{i}</math>. It is easy to see that <math>G(cd^{m},d)</math> is a '' | |||
Текущая версия от 12:03, 7 июня 2013
Circulant graph — циркулянтный граф.
1. Let [math]\displaystyle{ \,p }[/math] be a positive integer and [math]\displaystyle{ \,S }[/math] be a subset of [math]\displaystyle{ \{1,2, \ldots, p-1\} }[/math], such that [math]\displaystyle{ i \in S }[/math] implies [math]\displaystyle{ p-i \in S }[/math]. A circulant graph [math]\displaystyle{ \,G(p,S) }[/math] has vertices [math]\displaystyle{ 0,1, \ldots, p-1 }[/math] and two vertices [math]\displaystyle{ \,i }[/math] and [math]\displaystyle{ \,j }[/math] are adjacent if and only if [math]\displaystyle{ i - j \in S }[/math], where subtraction is carried out modulo [math]\displaystyle{ \,p }[/math]. The adjacency matrix of a circulant graph is a symmetric circulant.
2. (A circulant graph [math]\displaystyle{ \,G(n,d) }[/math]). The circulant graph [math]\displaystyle{ \,G(n,d) }[/math] with [math]\displaystyle{ d \geq 2 }[/math] is defined as follows. The vertex set is [math]\displaystyle{ V = \{0,1,2, \ldots, n-1\} }[/math], and the edge set is [math]\displaystyle{ E = \{(u,v)| \exists i, 0 \leq i \leq \lceil \log_{d}(n)\rceil - 1 }[/math], such that [math]\displaystyle{ u + d^{i} \equiv v\pmod{n}\} }[/math].
3. (A circulant graph [math]\displaystyle{ \,G(cd^{m},d) }[/math]). The circulant graph [math]\displaystyle{ \,G(cd^{m},d) }[/math] has [math]\displaystyle{ \,cd^{m} }[/math] vertices [math]\displaystyle{ \,(0 \lt c \lt d) }[/math]. [math]\displaystyle{ V = \{0, \ldots, cd^{m} - 1\} }[/math] is the set of vertices, and [math]\displaystyle{ E = \{(v,w), v, w \in V/\exists i, 0 \leq i \leq \lceil \log_{d}cd^{m}\rceil - 1, v \pm d^{i} \equiv w\pmod{cd^{m}}\}. }[/math] An edge between [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w = v \pm d^{i} }[/math] will have the label [math]\displaystyle{ d^{i} }[/math]. It is easy to see that [math]\displaystyle{ \,G(cd^{m},d) }[/math] is a Cayley graph defined on an abelian group.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.