# Cycle space

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

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.