Cycle space

Материал из WikiGrapp
Перейти к:навигация, поиск

Cycle spaceпространство циклов.

Given a graph \,G, let \,e_{1}, e_{2}, \ldots, e_{|E(G)|} be an ordering of its edges. Then a subset \,S of \,E(G) corresponds to a \,(0,1)-vector \,(b_{1}, \ldots, b_{|E(G)|}) in the usual way with \,b_{i}= 1 if \,e_{i} \in S, and \,b_{i} = 0 if \,e_{i} \not \in S. These vectors form an |E(G)|-dimensional vector space, denoted by (Z_{2})^{|E(G)|}, over the field of integers modulo \,2. The vectors in \,(Z_{2})^{|E(G)|} which correspond to the cycles in \,G generate a subspace called the cycle space of \,G denoted by \,{\mathcal C}(G). It is known that


\,\dim{\mathcal C}(G) = |E(G)| - |V(G)| + r


where \,r is the number of connected components.

See also

  • Basis number.

Литература

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