Cycle space

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 (0,1)-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 2. 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.