N-Звездный граф: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''<math>n</math>-Звездный граф''' (''<math></math>-Star graph'') - неориентированный граф <math>S_{n}</...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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>{\ | |||
==Литература== | ==Литература== | ||
* Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197. | |||
Текущая версия от 16:09, 18 февраля 2011
[math]\displaystyle{ n }[/math]-Звездный граф ([math]\displaystyle{ n }[/math]-Star graph) — неориентированный граф [math]\displaystyle{ \,S_{n} }[/math] с [math]\displaystyle{ \,n! }[/math] вершинами, помеченными [math]\displaystyle{ \,n! }[/math] перестановками на символах [math]\displaystyle{ \,1, 2, \ldots, n }[/math]. Между вершинами [math]\displaystyle{ \,u }[/math] и [math]\displaystyle{ \,v }[/math] существует ребро тогда и только тогда, когда существует транспозиция [math]\displaystyle{ \,\pi[1,i], \; 2 \leq i \leq n }[/math], такая, что [math]\displaystyle{ \,\pi[1,i](u) = v }[/math]. Граф [math]\displaystyle{ \,S_{n} }[/math] есть [math]\displaystyle{ \,(n-1) }[/math]-связный симметричный граф Кэлли. Граф [math]\displaystyle{ \,S_{n} }[/math] изоморфен диаграмме Хассе инверсионного частично упорядоченного множества [math]\displaystyle{ {\mathcal I}_{n} }[/math]
Литература
- Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197.