Граф Кэли

Не следует путать с графом Келли — шотландским дворянским титулом.

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

Определение

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

Предположим [math]\displaystyle{ S=S^{-1} }[/math], то есть [math]\displaystyle{ \forall s\in S\ \ \exist s^{-1}\in S }[/math].

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

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

Примеры

• 
  Граф Кэли свободной группы с двумя образующими a и b
• 
  Граф Кэли свободного произведения [math]\displaystyle{ \Z_2*\Z_3 }[/math]
• 
  Граф Кэли прямого произведения [math]\displaystyle{ \Z_2\times\Z_3 }[/math]

См. также

• Дерево Пифагора