Циркулянтный граф: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Циркулянтный граф''' (''Circulant graph'') - Пусть <math>p</math> --- натуральное число и пус...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Циркулянтный граф''' (''Circulant graph'') - | '''Циркулянтный граф''' (''[[Circulant graph]]'') - | ||
Пусть <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 | множества <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, | S</math>. Циркулянтный граф <math>G(p,S)</math> имеет в качестве [[вершина|вершин]] <math>0, 1, \ldots, | ||
p-1</math> и две вершины <math>i</math> и <math>j</math> смежны тогда и только тогда, когда <math>i - j | p-1</math> и две вершины <math>i</math> и <math>j</math> [[смежные вершины|смежны]] тогда и только тогда, когда <math>i - j | ||
\in S</math>, причем вычитание берется по модулю <math>p</math>. | \in S</math>, причем вычитание берется по модулю <math>p</math>. | ||
==Литература== | ==Литература== | ||
[Discrete Math.] | [Discrete Math.] | ||
Версия от 15:52, 7 мая 2010
Циркулянтный граф (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.]