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

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Cycle''' --- замкнутый маршрут, цикл, контур. '''1.''' A closed ''walk'', i.e. a walk such that the starting and ending vertices are t…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Cycle''' --- замкнутый маршрут, цикл, контур.  
'''Cycle''' — ''[[замкнутый маршрут]], [[цикл]], [[контур]].''


'''1.''' A closed ''walk'', i.e. a walk such that the starting and ending vertices
'''1.''' A [[closed walk|closed ''walk'']], i.e. a walk such that the starting and ending [[vertex|vertices]] are the same and all vertices in the walk are distinct is called is a '''cycle'''.
are the same and all vertices in the walk are distinct is called is a '''cycle'''.


Another name is '''Circuit'''.
Another name is '''[[Circuit]]'''.


'''2.''' For a directed graph, a closed path, i.e. a path <math>v_{0}, \ldots,
'''2.''' For a [[directed graph]], a closed path, i.e. a path <math>\,v_{0}, \ldots,v_{K}</math> is a '''cycle''' if <math>\,k > 1</math> and <math>v_{0} = v_{k}</math>.
v_{K}</math> is a '''cycle''' if <math>k > 1</math> and <math>v_{0} = v_{k}</math>.


'''3.''' The '''inverse cycle''' of a cycle <math>C = (v, v_{1}, \ldots,
'''3.''' The '''[[inverse cycle]]''' of a cycle <math>\,C = (v, v_{1}, \ldots,v_{n-1},v)</math> is the cycle <math>C^{-1} = (v, v_{n-1}, \ldots, v_{1}, v)</math>. Two cycles <math>\,C_{1} = (v_{1}, \ldots, v_{m})</math> and <math>C_{2} = (w_{1},\ldots, w_{m})</math> are called ''' equivalent''' if <math>\,w_{j} = v_{j+k}</math> for all <math>\,j</math>. The inverse cycle of <math>\,C</math> is not equivalent to <math>\,C</math>. Let <math>\,[C]</math> be the equivalence class which contains a cycle <math>\,C</math>. Let <math>\,B^{r}</math> be the cycle obtained by going <math>\,r</math> times around a cycle <math>\,B</math>. Such a cycle is called a multiple of <math>\,B</math>. A cycle <math>\,C</math> is '''primitive''' if both <math>\,C</math> and <math>\,C^{2}</math> have no backtracking (a backtracking is a subsequence of the form <math>\,..., x, y, x,...</math>), and it is not a multiple of a strictly  smaller cycle.
v_{n-1},v)</math> is the cycle <math>C^{-1} = (v, v_{n-1}, \ldots, v_{1}, v)</math>.
 
Two cycles <math>C_{1} = (v_{1}, \ldots, v_{m})</math> and <math>C_{2} = (w_{1},
==Литература==
\ldots, w_{m})</math> are called ''' equivalent''' if <math>w_{j} = v_{j+k}</math> for
 
all <math>j</math>. The inverse cycle of <math>C</math> is not equivalent to <math>C</math>. Let <math>[C]</math>
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.
be the equivalence class which contains a cycle <math>C</math>. Let <math>B^{r}</math> be
the cycle obtained by going <math>r</math> times around a cycle <math>B</math>. Such a
cycle is called a multiple of <math>B</math>. A cycle <math>C</math> is '''primitive''' if
both <math>C</math> and <math>C^{2}</math> have no backtracking (a backtracking is a
subsequence of the form <math>..., x, y, x,...</math>), and it is not a multiple of
a strictly  smaller cycle.

Навигация