Cycle space
|
|
In graph theory, certain vector spaces over the two-element field Z2 are associated with an undirected graph; this allows to use the tools of linear algebra to study graphs.
Let G be a finite simple undirected graph with edge set E. The power set of E becomes a Z2-vector space if we take the symmetric difference as addition. Every element of this vector space can be thought of as a linear combination of edges with coefficient from Z2. In yet another interpretation, the elements of this space are the functions E -> Z2. This is the edge space of G. Its zero is the empty set, and the one-element sets form a basis, so its dimension is equal to the number of edges of G.
An important subspace of the edge space is the cycle space. It is by definition the subspace generated by (the edge sets of) all the simple cycles of the graph. The addition of two cycles (shown dashed) is illustrated in the figure. Note that the result here (also shown dashed) is not a cycle but an edge-disjoint union of two simple cycles.
Missing image
Cycle_space_addition.png
Example for adding two cycles
There are a number of basic results concerning the cycle space. The symmetric difference of two simple cycles is again a simple cycle, or an edge-disjoint union of disjoint cycles. Using this observation, one can show that an edge set is in the cycle space if and only if it is a disjoint union of simple cycles. Phrased another way: the set F of edges is in the cycle space if and only if every vertex in the subgraph spanned by F has even degree.
It is not necessary to use all cycles to generate the cycle space: if G is connected and any spanning tree T of G is given, then the fundamental cycles of T form a basis of the cycle space. The dimension of the cycle space of a connected graph is thus related to the number of vertices and edges of the graph. If the graph has n vertices and m edges then the dimension is m-n+1.
An important application of the cycle space is Mac Lane's planarity criterion, which gives an algebraic characterization of the planar graphs.
References:
- R. Diestel, Graph Theory (2nd edition) (http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/download.html), Springer-Verlag, 2000