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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''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.

Текущая версия от 11:51, 1 ноября 2012

Cayley graphграф Кэли.

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

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

Литература

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