Circulant graph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Circulant graph''' --- циркулянтный граф. '''1.''' Let <math>p</math> be a positive integer and <math>S</math> be a subset of <math>\{1,2, \ldot…»)
 
Нет описания правки
 
Строка 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 ''Cauley graph'' defined on an abelian group.

Текущая версия от 10:44, 24 октября 2018

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.