Circuit

Материал из WEGA
Версия от 16:08, 2 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Circuit''' --- цикл. '''1.''' The same as ''Cycle''. '''2.''' Given a graph <math>G</math>, a '''circuit''' is a walk <math>(x_{1}, e_{1}, \ldots, x_{k}, e…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Circuit --- цикл.

1. The same as Cycle.

2. Given a graph [math]\displaystyle{ G }[/math], a circuit is a walk [math]\displaystyle{ (x_{1}, e_{1}, \ldots, x_{k}, e_{k}, x_{k+1}) }[/math] such that [math]\displaystyle{ x_{1}, \ldots, x_{k} }[/math] are distinct vertices, [math]\displaystyle{ e_{1}, \ldots, e_{k} }[/math] are distinct edges and [math]\displaystyle{ x_{1} = x_{k+1} }[/math]. If the graph is simple, we will denote it by [math]\displaystyle{ (x_{1}, \ldots, x_{k}) }[/math].

3. Given a hypergraph, a circuit is a sequence [math]\displaystyle{ (x_{1}, E_{1}, }[/math] [math]\displaystyle{ \ldots, }[/math] [math]\displaystyle{ x_{k} }[/math], [math]\displaystyle{ E_{k}) }[/math], where [math]\displaystyle{ x_{1}, \ldots, x_{k} }[/math] are distinct vertices, [math]\displaystyle{ E_{1}, \ldots, E_{k} }[/math] are distinct edges and [math]\displaystyle{ x_{i} \in E_{i} }[/math], [math]\displaystyle{ i = 1, \ldots, k }[/math], [math]\displaystyle{ x_{i+1} \in E_{i} }[/math], [math]\displaystyle{ i = 1, \ldots, k-1 }[/math], and [math]\displaystyle{ x_{1} \in E_{k} }[/math]. Here [math]\displaystyle{ k }[/math] is the length of this circuit.