N-Звездный граф

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

  • Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197.