Граф Кэли

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение

[править | править код]

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

Предположим , то есть .

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

Замечание: В случае если , вместо берут объединение .