N-Звездный граф: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''<math>n</math>-Звездный граф''' (''<math></math>-Star graph'') - неориентированный граф <math>S_{n}</...)
 
Нет описания правки
Строка 1: Строка 1:
'''<math>n</math>-Звездный граф''' (''<math></math>-Star graph'') -  
'''<math>n</math>-Звездный граф''' (''[[n-Star graph|<math>n</math>-Star graph]]'') - [[неориентированный граф]] <math>S_{n}</math>с <math>n!</math> [[вершина|вершинами]], помеченными <math>n!</math> перестановками на символах <math>1, 2, \ldots, n</math>. Между вершинами <math>u</math> и <math>v</math> существует [[ребро]] тогда и только тогда, когда существует транспозиция <math>\pi[1,i], \; 2 \leq i \leq n</math>, такая, что <math>\pi[1,i](u) = v</math>. Граф <math>S_{n}</math> есть <math>(n-1)</math>-[[связный граф|связный]] симметричный [[граф Кэлли]].
неориентированный граф <math>S_{n}</math>с <math>n!</math> вершинами, помеченными <math>n!</math>
[[Граф]] <math>S_{n}</math> [[изоморфные графы|изоморфен]] [[диаграмма Хассе|диаграмме Хассе]] инверсионного частично упорядоченного множества <math>{\mathcal I}_{n}</math>
перестановками на символах <math>1, 2, \ldots, n</math>. Между вершинами <math>u</math> и
<math>v</math> существует ребро тогда и только тогда, когда существует
транспозиция <math>\pi[1,i], \; 2 \leq i \leq n</math>, такая, что <math>\pi[1,i](u) =
v</math>. Граф <math>S_{n}</math>есть <math>(n-1)</math>-связный симметричный граф Кэлли.
Граф <math>S_{n}</math>изоморфен диаграмме Хассе инверсионного частично
упорядоченного множества <math>{\cal I}_{n}</math>
==Литература==
==Литература==
[WG'96]
[WG'96]

Навигация