# 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 $\,v_{0}, \ldots,v_{K}$ is a cycle if $\,k > 1$ and $v_{0} = v_{k}$.

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

## Литература

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