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