The Binary Cycle Space
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, identity function as negation, and empty set as zero. The one-element sets form a basis, so its dimension is equal to the number of edges of G. Because every element of this vector space is a subset of E, it can be regarded as an indicator function of type, then this vector space coincide with the free Z2-module with basis E. This is the (binary) edge space of G.
An important subspace of the edge space is the (binary) 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 simple cycle but an edge-disjoint union of two simple cycles.
There are a number of basic results concerning the cycle space. The symmetric difference of two simple cycles is either a simple cycle or a union of edge-disjoint simple 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, known as a cycle basis. 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. In a planar graph, the set of interior faces of an embedding of the graph also provides a cycle basis.
An important application of the cycle space are Whitney's planarity criterion and Mac Lane's planarity criterion, which give an algebraic characterization of the planar graphs.
Read more about this topic: Cycle Space
Famous quotes containing the words cycle and/or space:
“The lifelong process of caregiving, is the ultimate link between caregivers of all ages. You and I are not just in a phase we will outgrow. This is life—birth, death, and everything in between.... The care continuum is the cycle of life turning full circle in each of our lives. And what we learn when we spoon-feed our babies will echo in our ears as we feed our parents. The point is not to be done. The point is to be ready to do again.”
—Paula C. Lowe (20th century)
“As photographs give people an imaginary possession of a past that is unreal, they also help people to take possession of space in which they are insecure.”
—Susan Sontag (b. 1933)