Associated Cayley digraph

Associated Cayley digraph — соотнесённый орграф Кэли.

Let [math]\displaystyle{ \,\Gamma }[/math] be a group and [math]\displaystyle{ \,S }[/math] be a generating set of [math]\displaystyle{ \,\Gamma }[/math] such that

(1) [math]\displaystyle{ e \not \in S }[/math], [math]\displaystyle{ \,e }[/math] is the identity in [math]\displaystyle{ \,\Gamma }[/math],

(2) [math]\displaystyle{ s \in S \Leftrightarrow s^{-1} \in S }[/math].

The associated Cayley digraph [math]\displaystyle{ \,Cay(\Gamma,S) }[/math] is a digraph whose vertices are the elements of [math]\displaystyle{ \,\Gamma }[/math] and arcs are the couples [math]\displaystyle{ \,(x,sx) }[/math] for [math]\displaystyle{ x \in \Gamma }[/math] and [math]\displaystyle{ s \in S }[/math].

With this definition, [math]\displaystyle{ \,Cay(\Gamma,S) }[/math] is a connected symmetric digraph (in fact, a strongly connected digraph).

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.