Циркулянтный граф

Циркулянтный граф (Circulant graph) — Пусть [math]\displaystyle{ \,p }[/math] — натуральное число и пусть [math]\displaystyle{ \,S }[/math] — подмножество множества [math]\displaystyle{ \{1, 2, \ldots, p-1\} }[/math] такое, что [math]\displaystyle{ i \in S }[/math] влечет [math]\displaystyle{ p-i \in S. }[/math] Циркулянтный граф [math]\displaystyle{ \,G(p,S) }[/math] имеет в качестве вершин [math]\displaystyle{ 0, 1, \ldots, p-1 }[/math] и две вершины [math]\displaystyle{ \,i }[/math] и [math]\displaystyle{ \,j }[/math] смежны тогда и только тогда, когда [math]\displaystyle{ \,i - j \in S }[/math], причем вычитание берется по модулю [math]\displaystyle{ \,p. }[/math]

Литература

• [Discrete Math.]