Граф Кэли
Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.
Определение
Пусть дана дискретная группа G {displaystyle G} и система образующих S {displaystyle S} .
Предположим S = S − 1 {displaystyle S=S^{-1}} , то есть, для каждого s ∈ S , ∃ s − 1 ∈ S {displaystyle sin S,exists s^{-1}in S} .
Графом Кэли группы G {displaystyle G} по системе образующих S {displaystyle S} является граф, вершинами которого являются элементы группы и элемент g {displaystyle g} соединён ребром в точности с теми элементами, которые получаются домножением g {displaystyle g} на элемент из S {displaystyle S} .
Замечание: В случае если S ≠ S − 1 {displaystyle S ot =S^{-1}} , вместо S {displaystyle S} берут объединение S ∪ S − 1 {displaystyle Scup S^{-1}} .
Примеры
-
Граф Кэли свободной группы с двумя образующими a и b
-
Граф Кэли свободного произведения Z 2 ∗ Z 3 {displaystyle mathbb {Z} _{2}*mathbb {Z} _{3}}
-
Граф Кэли прямого произведения Z 2 × Z 3 {displaystyle mathbb {Z} _{2} imes mathbb {Z} _{3}}