4634
правки
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. | |||