Циркулянтный граф: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Циркулянтный граф''' (''Circulant graph'') - Пусть <math>p</math> --- натуральное число и пус...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Циркулянтный граф''' (''Circulant graph'') -
'''Циркулянтный граф''' (''[[Circulant graph]]'') Пусть <math>\,p</math> натуральное число и пусть <math>\,S</math> подмножество множества <math>\{1, 2, \ldots, p-1\}</math> такое, что <math>i \in S</math> влечет <math>p-i \in S.</math> Циркулянтный граф <math>\,G(p,S)</math> имеет в качестве [[вершина|вершин]] <math>0, 1, \ldots, p-1</math> и две вершины <math>\,i</math> и <math>\,j</math> [[смежные вершины|смежны]] тогда и только тогда, когда <math>\,i - j \in S</math>, причем вычитание берется по модулю <math>\,p.</math>
Пусть <math>p</math> --- натуральное число и пусть <math>S</math> --- подмножество
множества <math>\{1, 2, \ldots, p-1\}</math> такое, что <math>i \in S</math> влечет <math>p-i \in
S</math>. Циркулянтный граф <math>G(p,S)</math> имеет в качестве вершин <math>0, 1, \ldots,
p-1</math> и две вершины <math>i</math> и <math>j</math> смежны тогда и только тогда, когда <math>i - j
\in S</math>, причем вычитание берется по модулю <math>p</math>.
==Литература==
==Литература==
[Discrete Math.]
* [Discrete Math.]

Текущая версия от 12:54, 30 сентября 2011

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