N-Star graph

Материал из WikiGrapp
Версия от 14:23, 28 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''<math>n</math>-Star graph''' --- <math>n</math>-звездный граф. The ''' <math>n</math>-star graph''' <math>S_{n}</math> is an undirected graph consi…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[math]\displaystyle{ n }[/math]-Star graph --- [math]\displaystyle{ n }[/math]-звездный граф.

The [math]\displaystyle{ n }[/math]-star graph [math]\displaystyle{ S_{n} }[/math] is an undirected graph consisting of [math]\displaystyle{ n! }[/math] nodes labeled with [math]\displaystyle{ n! }[/math] permutations on symbols [math]\displaystyle{ 1, 2, \ldots, n }[/math]. There is an edge between two nodes [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] in [math]\displaystyle{ S_{n} }[/math] if and only if there is a transposition [math]\displaystyle{ \pi[1,i], \; 2 \leq i \leq n }[/math], such that [math]\displaystyle{ \pi[1,i](u) = v }[/math]. The [math]\displaystyle{ n }[/math]-star graph is an [math]\displaystyle{ (n-1) }[/math]-connected vertex-symmetric Cayley graph (with the generating set [math]\displaystyle{ \{\pi[1,2], \pi[1,3], \ldots, \pi[1,n]\} }[/math] for the symmetric group of order [math]\displaystyle{ n }[/math]).