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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''Associated Cayley digraph''' --- соотнесённый орграф Кэли. Let <math>\Gamma</math> be a group and <math>S</math> be a generating set of …»)
 
Нет описания правки
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
'''Associated Cayley digraph''' --- соотнесённый орграф Кэли.   
'''Associated Cayley digraph''' — ''[[соотнесённый орграф Кэли]].''  


Let <math>\Gamma</math>  be a group and <math>S</math> be a generating set of <math>\Gamma</math> such that
Let <math>\,\Gamma</math>  be a group and <math>\,S</math> be a generating set of <math>\,\Gamma</math> such that


(1) <math>e \not \in S</math>, <math>e</math> is the identity in <math>\Gamma</math>,
(1) <math>e \not \in S</math>, <math>\,e</math> is the identity in <math>\,\Gamma</math>,


(2) <math>s \in S \Leftrightarrow s^{-1} \in S</math>.
(2) <math>s \in S \Leftrightarrow s^{-1} \in S</math>.




The '''associated Cayley digraph''' <math>Cay(\Gamma,S)</math> is a digraph
The '''associated Cayley digraph''' <math>\,Cay(\Gamma,S)</math> is a digraph
whose vertices are the elements of <math>\Gamma</math> and arcs are the
whose [[vertex|vertices]] are the elements of <math>\,\Gamma</math> and [[arc|arcs]] are the
couples <math>(x,sx)</math> for <math>x \in \Gamma</math> and <math>s \in S</math>.
couples <math>\,(x,sx)</math> for <math>x \in \Gamma</math> and <math>s \in S</math>.


With this definition, <math>Cay(\Gamma,S)</math> is a connected symmetric digraph
With this definition, <math>\,Cay(\Gamma,S)</math> is a connected symmetric [[digraph]]
(in fact, a strongly connected digraph).
(in fact, a strongly connected digraph).
==Литература==
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 16:12, 19 декабря 2011

Associated Cayley digraphсоотнесённый орграф Кэли.

Let [math]\displaystyle{ \,\Gamma }[/math] be a group and [math]\displaystyle{ \,S }[/math] be a generating set of [math]\displaystyle{ \,\Gamma }[/math] such that

(1) [math]\displaystyle{ e \not \in S }[/math], [math]\displaystyle{ \,e }[/math] is the identity in [math]\displaystyle{ \,\Gamma }[/math],

(2) [math]\displaystyle{ s \in S \Leftrightarrow s^{-1} \in S }[/math].


The associated Cayley digraph [math]\displaystyle{ \,Cay(\Gamma,S) }[/math] is a digraph whose vertices are the elements of [math]\displaystyle{ \,\Gamma }[/math] and arcs are the couples [math]\displaystyle{ \,(x,sx) }[/math] for [math]\displaystyle{ x \in \Gamma }[/math] and [math]\displaystyle{ s \in S }[/math].

With this definition, [math]\displaystyle{ \,Cay(\Gamma,S) }[/math] is a connected symmetric digraph (in fact, a strongly connected digraph).

Литература

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