Просмотр кода страницы Cycle space

'''Cycle space''' — ''[[пространство циклов]].'' 

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
<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


:::<math>\,\dim{\mathcal C}(G) = |E(G)| - |V(G)| + r</math>


where <math>\,r</math> is the number of connected components.

==See also==

* ''Basis number''.

==Литература==

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