Cycle

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.