Cycle space: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Cycle space''' --- пространство циклов. Given a graph <math>G</math>, let <math>e_{1}, e_{2}, \ldots, e_{|E(G)|}</math> be an ordering of its …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Cycle space''' | '''Cycle space''' — ''[[пространство циклов]].'' | ||
Given a graph <math>G</math>, let <math>e_{1}, e_{2}, \ldots, e_{|E(G)|}</math> be an | Given a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math>, let <math>\,e_{1}, e_{2}, \ldots, e_{|E(G)|}</math> be an ordering of its [[edge|edges]]. Then a subset <math>\,S</math> of <math>\,E(G)</math> corresponds to a <math>\,(0,1)</math>-vector <math>\,(b_{1}, \ldots, b_{|E(G)|})</math> in the usual way with <math>\,b_{i}= 1</math> if <math>\,e_{i} \in S</math>, and <math>\,b_{i} = 0</math> if <math>\,e_{i} \not \in S</math>. These vectors form an <math>|E(G)|</math>-dimensional vector space, denoted by | ||
ordering of its edges. Then a subset <math>S</math> of <math>E(G)</math> corresponds to a | <math>(Z_{2})^{|E(G)|}</math>, over the field of integers modulo <math>\,2</math>. The vectors in <math>\,(Z_{2})^{|E(G)|}</math> which correspond to the [[cycle|cycles]] in <math>\,G</math> generate a subspace called the '''cycle space''' of <math>\,G</math> denoted by <math>\,{\mathcal C}(G)</math>. It is known that | ||
(0,1)-vector <math>(b_{1}, \ldots, b_{|E(G)|})</math> in the usual way with <math>b_{i} | |||
= 1</math> if <math>e_{i} \in S</math>, and <math>b_{i} = 0</math> if <math>e_{i} \not \in S</math>. These vectors form an <math>|E(G)|</math>-dimensional vector space, denoted by | |||
<math>(Z_{2})^{|E(G)|}</math>, over the field of integers modulo 2. The vectors | |||
in <math>(Z_{2})^{|E(G)|}</math> which | |||
correspond to the cycles in <math>G</math> generate a subspace called the '''cycle space''' of <math>G</math> denoted by <math>{\mathcal C}(G)</math>. It is known that | |||
where <math>r</math> is the number of connected components. | :::<math>\,\dim{\mathcal C}(G) = |E(G)| - |V(G)| + r</math> | ||
where <math>\,r</math> is the number of connected components. | |||
==See also== | ==See also== | ||
*''Basis number''. | |||
* ''Basis number''. | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 13:21, 22 декабря 2021
Cycle space — пространство циклов.
Given a graph [math]\displaystyle{ \,G }[/math], let [math]\displaystyle{ \,e_{1}, e_{2}, \ldots, e_{|E(G)|} }[/math] be an ordering of its edges. Then a subset [math]\displaystyle{ \,S }[/math] of [math]\displaystyle{ \,E(G) }[/math] corresponds to a [math]\displaystyle{ \,(0,1) }[/math]-vector [math]\displaystyle{ \,(b_{1}, \ldots, b_{|E(G)|}) }[/math] in the usual way with [math]\displaystyle{ \,b_{i}= 1 }[/math] if [math]\displaystyle{ \,e_{i} \in S }[/math], and [math]\displaystyle{ \,b_{i} = 0 }[/math] if [math]\displaystyle{ \,e_{i} \not \in S }[/math]. These vectors form an [math]\displaystyle{ |E(G)| }[/math]-dimensional vector space, denoted by [math]\displaystyle{ (Z_{2})^{|E(G)|} }[/math], over the field of integers modulo [math]\displaystyle{ \,2 }[/math]. The vectors in [math]\displaystyle{ \,(Z_{2})^{|E(G)|} }[/math] which correspond to the cycles in [math]\displaystyle{ \,G }[/math] generate a subspace called the cycle space of [math]\displaystyle{ \,G }[/math] denoted by [math]\displaystyle{ \,{\mathcal C}(G) }[/math]. It is known that
- [math]\displaystyle{ \,\dim{\mathcal C}(G) = |E(G)| - |V(G)| + r }[/math]
where [math]\displaystyle{ \,r }[/math] is the number of connected components.
See also
- Basis number.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.