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

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

Текущая версия от 17:21, 14 декабря 2021

Cycleзамкнутый маршрут, цикл, контур.

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

Another name is Circuit.

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

3. The inverse cycle of a cycle [math]\displaystyle{ \,C = (v, v_{1}, \ldots,v_{n-1},v) }[/math] is the cycle [math]\displaystyle{ C^{-1} = (v, v_{n-1}, \ldots, v_{1}, v) }[/math]. Two cycles [math]\displaystyle{ \,C_{1} = (v_{1}, \ldots, v_{m}) }[/math] and [math]\displaystyle{ C_{2} = (w_{1},\ldots, w_{m}) }[/math] are called equivalent if [math]\displaystyle{ \,w_{j} = v_{j+k} }[/math] for all [math]\displaystyle{ \,j }[/math]. The inverse cycle of [math]\displaystyle{ \,C }[/math] is not equivalent to [math]\displaystyle{ \,C }[/math]. Let [math]\displaystyle{ \,[C] }[/math] be the equivalence class which contains a cycle [math]\displaystyle{ \,C }[/math]. Let [math]\displaystyle{ \,B^{r} }[/math] be the cycle obtained by going [math]\displaystyle{ \,r }[/math] times around a cycle [math]\displaystyle{ \,B }[/math]. Such a cycle is called a multiple of [math]\displaystyle{ \,B }[/math]. A cycle [math]\displaystyle{ \,C }[/math] is primitive if both [math]\displaystyle{ \,C }[/math] and [math]\displaystyle{ \,C^{2} }[/math] have no backtracking (a backtracking is a subsequence of the form [math]\displaystyle{ \,..., x, y, x,... }[/math]), and it is not a multiple of a strictly smaller cycle.

Литература

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