Граф Кэли

Не следует путать с графом Келли — шотландским дворянским титулом.

Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.

Определение

Пусть дана дискретная группа $G$ и система образующих $S$.

Предположим $S=S^{-1}$, то есть $\mathrm{\forall }s\in S\mathrm{\exists }{s}^{-1}\in S$.

Графом Кэли группы $G$ по системе образующих $S$ является граф, вершинами которого являются элементы группы, и элемент $g$ соединён ребром в точности с теми элементами, которые получаются домножением $g$ на элемент из $S$.

Замечание: В случае если $S=S^{-1}$, вместо $S$ берут объединение $S\cup S^{-1}$.

Примеры

• 
  Граф Кэли свободной группы с двумя образующими a и b
• 
  Граф Кэли свободного произведения ${\mathbb{\mathbb{Z}}}_2*{\mathbb{\mathbb{Z}}}_3$
• 
  Граф Кэли прямого произведения ${\mathbb{\mathbb{Z}}}_2\times {\mathbb{\mathbb{Z}}}_3$

См. также

• Дерево Пифагора