Граф Кэли

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

Определение

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

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

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

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

Примеры

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

См. также