Просмотр кода страницы Circulant graph

'''Circulant graph''' — ''[[циркулянтный граф]].'' 

'''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''.

'''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
\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 <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.

==Литература==

* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.