# Cayley graph

Перейти к:навигация, поиск

Cayley graphграф Кэли.

1. Let $Z_{n} = \{0, 1, \ldots, n-1\}$ be an additive abelian group of integers modulo $\,n$, and $\,H$ be a subset of $\,Z_{n}$ with $0 \not \in H$. Then the Cayley graph $C_{Z_{n},H}$ is an undirected graph with $V(C_{Z_{n},H}) = Z_{n}$, and $E(C_{Z_{n},H}) = \{(x,x+y): \; x \in Z_{n}, y \in H$ and the addition is taken modulo $\,n\}$. The adjacency matrix of $C_{Z_{n},H}$ is $n \times n$ symmetric circulant with entries 0 and 1.

2. Let $\,\Gamma$ be a finite group and $\,S$ be a symmetric generator set of $\,\Gamma$, i.e. $\langle S \rangle = \Gamma, \; s \in S \Rightarrow s^{-1} \in S\mbox{ and }1_{\Gamma} \not \in S$. The Cayley graph $\,G_{S}(\Gamma)$ is defined as an undirected graph with its vertex set $\,V = \Gamma$ and edge set $E = \{(g,h)| \; g^{-1}h \in S\}$.

## Литература

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