Cayley graph

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

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.