Аноним

Cayley graph: различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''Cayley graph''' --- граф Кэли. '''1.''' Let <math>Z_{n} = \{0, 1, \ldots, n-1\}</math> be an additive abelian group of integers modulo <math>n</math>, a…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Cayley graph''' --- граф Кэли.  
'''Cayley graph''' — [[граф Кэли]].  


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


'''2.''' Let <math>\Gamma</math> be a finite group and <math>S</math> be a symmetric generator set
'''2.''' Let <math>\,\Gamma</math> be a finite group and <math>\,S</math> be a symmetric generator set
of <math>\Gamma</math>, i.e. <math>\langle S \rangle = \Gamma, \; s \in S \Rightarrow
of <math>\,\Gamma</math>, i.e. <math>\langle S \rangle = \Gamma, \; s \in S \Rightarrow
s^{-1} \in S\mbox{ and }1_{\Gamma} \not \in S</math>. The '''Cayley graph'''
s^{-1} \in S\mbox{ and }1_{\Gamma} \not \in S</math>. The '''Cayley graph'''
<math>G_{S}(\Gamma)</math> is defined as an undirected graph with its vertex set <math>V
<math>\,G_{S}(\Gamma)</math> is defined as an undirected graph with its [[vertex]] set <math>\,V
= \Gamma</math> and edge set <math>E = \{(g,h)| \; g^{-1}h \in S\}</math>.
= \Gamma</math> and [[edge]] set <math>E = \{(g,h)| \; g^{-1}h \in S\}</math>.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.