Circuit: различия между версиями
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…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Circuit''' | '''Circuit''' — ''[[цикл]].'' | ||
'''1.''' The same as ''Cycle''. | '''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_{k}, | '''2.''' Given a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math>, a '''circuit''' is a walk <math>(x_{1}, e_{1}, \ldots, x_{k}, e_{k}, | ||
x_{k+1})</math> such that <math>x_{1}, \ldots, x_{k}</math> are distinct vertices, | x_{k+1})</math> such that <math>x_{1}, \ldots, x_{k}</math> are distinct [[vertex|vertices]], | ||
<math>e_{1}, \ldots, e_{k}</math> are distinct edges and <math>x_{1} = x_{k+1}</math>. If | <math>e_{1}, \ldots, e_{k}</math> are distinct [[edge|edges]] and <math>\,x_{1} = x_{k+1}</math>. If | ||
the graph is ''simple'', we will denote it by <math>(x_{1}, \ldots, | the graph is ''[[simple graph|simple]]'', we will denote it by <math>(x_{1}, \ldots, | ||
x_{k})</math>. | x_{k})</math>. | ||
'''3.''' Given a hypergraph, a '''circuit''' is a sequence <math>(x_{1}, E_{1}, | '''3.''' Given a [[hypergraph]], a '''circuit''' is a sequence <math>(x_{1}, E_{1},\ldots,x_{k}, E_{k})</math>, where <math>x_{1}, \ldots, x_{k}</math> are distinct vertices, <math>E_{1}, | ||
\ldots, E_{k}</math> are distinct edges and <math>x_{i} \in E_{i}</math>, <math>i = 1, | \ldots, E_{k}</math> are distinct edges and <math>x_{i} \in E_{i}</math>, <math>i = 1, | ||
\ldots, k</math>, <math>x_{i+1} \in E_{i}</math>, <math>i = 1, \ldots, k-1</math>, and <math>x_{1} \in | \ldots, k</math>, <math>x_{i+1} \in E_{i}</math>, <math>i = 1, \ldots, k-1</math>, and <math>x_{1} \in | ||
E_{k}</math>. Here <math>k</math> is the length of this circuit. | E_{k}</math>. Here <math>\,k</math> is the length of this circuit. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 12:10, 5 июня 2013
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.