Граф Кэли
Из Википедии, бесплатной энциклопедии
Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.
Определение[править | править код]
Пусть дана дискретная группа и система образующих .
Предположим , то есть .
Графом Кэли группы по системе образующих является граф, вершинами которого являются элементы группы, и элемент соединён ребром в точности с теми элементами, которые получаются домножением на элемент из .
Замечание: В случае если , вместо берут объединение .
Примеры[править | править код]
- Граф Кэли свободной группы с двумя образующими a и b
- Граф Кэли свободного произведения
- Граф Кэли прямого произведения