Circuit

Материал из WikiGrapp
Версия от 12:10, 5 июня 2013; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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},\ldots,x_{k}, 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.

Литература

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