Cycle

Материал из WEGA
Версия от 15:34, 18 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Cycle''' --- замкнутый маршрут, цикл, контур. '''1.''' A closed ''walk'', i.e. a walk such that the starting and ending vertices are t…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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.