The binary cycle space

In graph theory, certain vector spaces over the two-element field Z₂ are associated with an undirected graph; this allows one to use the tools of linear algebra to study graphs. A diagram of a graph with 6 vertices and 7 edges. ... A vector space (or linear space) is the basic object of study in the branch of mathematics called linear algebra. ... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... A diagram of a graph with 6 vertices and 7 edges. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (or linear spaces), linear transformations, and systems of linear equations. ...

Let G be a finite simple undirected graph with edge set E. The power set of E becomes a Z₂-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 Z₂. In yet another interpretation, the elements of this space are the functions E -> Z₂. This is the (binary) 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. In mathematics, a set S, the power set of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... In mathematics, the symmetric difference of two sets is the set of elements which are in one of either set, but not in both. ... In mathematics, linear combinations are a concept central to linear algebra and related fields of mathematics. ... In mathematics, the empty set is the set with no elements. ... In mathematics, a subset B of a vector space V is said to be a basis of V if it satisfies one of the four equivalent conditions: B is both a set of linearly independent vectors and a generating set of V. B is a minimal generating set of V... In mathematics, the dimension of a vector space V is the cardinality (i. ...

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. The concept of a linear subspace (or vector subspace) is important in linear algebra and related fields of mathematics. ... In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ...

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. Image File history File links Example for addition in the cycle space File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ...

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. A diagram of a graph with 6 vertices and 7 edges. ... In mathematics, a subset B of a vector space V is said to be a basis of V if it satisfies one of the four equivalent conditions: B is both a set of linearly independent vectors and a generating set of V. B is a minimal generating set of V... In mathematics, the dimension of a vector space V is the cardinality (i. ...

An important application of the cycle space is Mac Lane's planarity criterion, which gives an algebraic characterization of the planar graphs. In graph theory, Mac Lanes planarity criterion is a characterisation of planar graphs in terms of their cycle spaces. ... In graph theory, a planar graph is a graph that can be embedded in a plane so that no edges intersect. ...

The integral cycle space

The foregoing development can be carried out over the integers, Z. The integral edge space is the abelian group Z^E of functions from the edge set E to the integers. It is necessary (for the notation) to choose an arbitrary orientation of the graph in order to define the cycle space, but the definition does not depend on that choice. An integral cycle is a function such that the sum of values on edges oriented into a vertex x equals the sum of values on edges oriented out of x, for every vertex x. The set of integral cycles is a subgroup of the integral edge space. A cycle that never takes the value zero is called nowhere zero. In mathematics, an abelian group, also called a commutative group, is a group (G, *) such that a * b = b * a for all a and b in G. Abelian groups are named after Niels Henrik Abel. ... This article just presents the basic definitions. ...

Reversing the orientation of an edge negates the value of a cycle on that edge. It is in this sense that the theory is independent of the arbitrary orientation. Given any one cycle, the orientation can be chosen so that cycle takes only nonnegative values.

An integral cycle whose maximum absolute value on any edge is less than k, a positive integer, is sometimes called a k-flow on G. W.T. Tutte developed an extensive theory of nowhere-zero k-flows that is in some ways dual to that of graph coloring. William Thomas Tutte (May 14, 1917–May 2, 2002) was a British, later Canadian, codebreaker and mathematician. ... A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ...

The cycle space over a field or commutative ring

The construction of the integral cycle space can be carried out for any field, abelian group, or (most generally) commutative ring (with unity) R replacing the integers. If R is a field, the cycle space is a vector space over R with dimension m - n + c, where c is the number of connected components of G. If R is any commutative ring, the cycle space is a free R-module with rank m - n + c. Look up field in Wiktionary, the free dictionary A green field or paddock Field may refer to: A field is an open land area, used for growing agricultural crops. ... In mathematics, an abelian group, also called a commutative group, is a group (G, *) such that a * b = b * a for all a and b in G. Abelian groups are named after Niels Henrik Abel. ... In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation obeys the commutative law. ... A vector space (or linear space) is the basic object of study in the branch of mathematics called linear algebra. ... A module is a self-contained component of a system, which has a well-defined interface to the other components; something is modular if it is constructed so as to facilitate easy assembly, flexible arrangement, and/or repair of the components. ...

When R is an abelian group such a cycle may also be called an R-flow on G. Nowhere-zero R-flows for a finite abelian group R of k elements are related to nowhere-zero integral k-flows in Tutte's theory. The number of nowhere-zero R-cycles is an evaluation of the Tutte polynomial, dual to the number of proper colorings of the graph (Tutte, 1984, Section IX.4).

References

• R. Diestel, Graph Theory (2nd edition), Springer-Verlag, Berlin, 2000.

• W.T. Tutte, Graph Theory, Addison-Wesley, Reading, Mass., 1984. See Chapter VIII.