Cayley graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''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…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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.