Cycle

Материал из WikiGrapp
Перейти к:навигация, поиск

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.