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

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

'''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'''.

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

'''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>.

'''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.

 

 

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