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

Материал из WEGA

Циркулянтный граф (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.]