Граф Кэли

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

Определение

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

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

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

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

Примеры

• 

  Граф Кэли свободной группы с двумя образующими a и b

• 

  Граф Кэли свободного произведения ${\displaystyle \mathbb {Z} _{2}*\mathbb {Z} _{3}}$

• 

  Граф Кэли прямого произведения ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{3}}$

См. также

• Дерево Пифагора
• Граф циклов

Эта страница в последний раз была отредактирована 13 июля 2023 в 15:40.