Cycle space

This article is about a concept in graph theory. For space allocated to bicycles, see cycling infrastructure.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

This set of subgraphs can be described algebraically as a vector space over the two-element finite field. The dimension of this space is the circuit rank of the graph. The same space can also be described in terms from algebraic topology as the first homology group of the graph. Using homology theory, the binary cycle space may be generalized to cycle spaces over arbitrary rings.

Definitions

The cycle space of a graph can be described with increasing levels of mathematical sophistication as a set of subgraphs, as a binary vector space, or as a homology group.

Graph theory

A spanning subgraph of a given graph G may be defined from any subset S of the edges of G. The subgraph has the same set of vertices as G itself (this is the meaning of the word "spanning") but has the elements of S as its edges. Thus, a graph G with m edges has 2^m spanning subgraphs, including G itself as well as the empty graph on the same set of vertices as G. The collection of all spanning subgraphs of a graph G forms the edge space of G. ^{[1] [2]}

A graph G, or one of its subgraphs, is said to be Eulerian if each of its vertices has an even number of incident edges (this number is called the degree of the vertex). This property is named after Leonhard Euler who proved in 1736, in his work on the Seven Bridges of Königsberg, that a connected graph has a tour that visits each edge exactly once if and only if it is Eulerian. However, for the purposes of defining cycle spaces, an Eulerian subgraph does not need to be connected; for instance, the empty graph, in which all vertices are disconnected from each other, is Eulerian in this sense. The cycle space of a graph is the collection of its Eulerian spanning subgraphs. ^{[1] [2]}

Algebra

If one applies any set operation such as union or intersection of sets to two spanning subgraphs of a given graph, the result will again be a subgraph. In this way, the edge space of an arbitrary graph can be interpreted as a Boolean algebra. ^[3]

The symmetric difference of two Eulerian subgraphs (red and green) is a Eulerian subgraph (blue).

The cycle space, also, has an algebraic structure, but a more restrictive one. The union or intersection of two Eulerian subgraphs may fail to be Eulerian. However, the symmetric difference of two Eulerian subgraphs (the graph consisting of the edges that belong to exactly one of the two given graphs) is again Eulerian. ^[1] This follows from the fact that the symmetric difference of two sets with an even number of elements is also even. Applying this fact separately to the neighbourhoods of each vertex shows that the symmetric difference operator preserves the property of being Eulerian.

A family of sets closed under the symmetric difference operation can be described algebraically as a vector space over the two-element finite field ${\displaystyle \mathbb {Z} _{2}}$. ^[4] This field has two elements, 0 and 1, and its addition and multiplication operations can be described as the familiar addition and multiplication of integers, taken modulo 2. A vector space consists of a set of elements together with an addition and scalar multiplication operation satisfying certain properties generalizing the properties of the familiar real vector spaces. For the cycle space, the elements of the vector space are the Eulerian subgraphs, the addition operation is symmetric differencing, multiplication by the scalar 1 is the identity operation, and multiplication by the scalar 0 takes every element to the empty graph, which forms the additive identity element for the cycle space.

The edge space is also a vector space over ${\displaystyle \mathbb {Z} _{2}}$ with the symmetric difference as addition. As vector spaces, the cycle space and the cut space of the graph (the family of edge sets that span the cuts of the graph) are the orthogonal complements of each other within the edge space. This means that a set ${\displaystyle S}$ of edges in a graph forms a cut if and only if every Eulerian subgraph has an even number of edges in common with ${\displaystyle S}$, and ${\displaystyle S}$ forms an Eulerian subgraph if and only if every cut has an even number of edges in common with ${\displaystyle S}$. ^[2] Although these two spaces are orthogonal complements, some graphs have nonempty subgraphs that belong to both of them. Such a subgraph (an Eulerian cut) exists as part of a graph ${\displaystyle G}$ if and only if ${\displaystyle G}$ has an even number of spanning forests. ^[5]

Topology

An undirected graph may be viewed as a simplicial complex with its vertices as zero-dimensional simplices and the edges as one-dimensional simplices. ^[6] The chain complex of this topological space consists of its edge space and vertex space (the Boolean algebra of sets of vertices), connected by a boundary operator that maps any spanning subgraph (an element of the edge space) to its set of odd-degree vertices (an element of the vertex space). The homology group

${\displaystyle H_{1}(G,\mathbb {Z} _{2})}$

consists of the elements of the edge space that map to the zero element of the vertex space; these are exactly the Eulerian subgraphs. Its group operation is the symmetric difference operation on Eulerian subgraphs.

Replacing ${\displaystyle \mathbb {Z} _{2}}$ in this construction by an arbitrary ring allows the definition of cycle spaces to be extended to cycle spaces with coefficients in the given ring, that form modules over the ring. ^[7] In particular, the integral cycle space is the space

${\displaystyle H_{1}(G,\mathbb {Z} ).}$

It can be defined in graph-theoretic terms by choosing an arbitrary orientation of the graph, and defining an integral cycle of a graph ${\displaystyle G}$ to be an assignment of integers to the edges of ${\displaystyle G}$ (an element of the free abelian group over the edges) with the property that, at each vertex, the sum of the numbers assigned to incoming edges equals the sum of the numbers assigned to outgoing edges. ^[8]

A member of ${\displaystyle H_{1}(G,\mathbb {Z} )}$ or of ${\displaystyle H_{1}(G,\mathbb {Z} _{k})}$ (the cycle space modulo ${\displaystyle k}$) with the additional property that all of the numbers assigned to the edges are nonzero is called a nowhere-zero flow or a nowhere-zero ${\displaystyle k}$-flow respectively. ^[9]

Circuit rank

Main article: Circuit rank

As a vector space, the dimension of the cycle space of a graph with ${\displaystyle n}$ vertices, ${\displaystyle m}$ edges, and ${\displaystyle c}$ connected components is ${\displaystyle m-n+c}$. ^{[1] [2] [10]} This number can be interpreted topologically as the first Betti number of the graph. ^[6] In graph theory, it is known as the circuit rank, cyclomatic number, or nullity of the graph.

Combining this formula for the rank with the fact that the cycle space is a vector space over the two-element field shows that the total number of elements in the cycle space is exactly ${\displaystyle 2^{m-n+c}}$.

Cycle bases

Main article: Cycle basis

A basis of a vector space is a minimal subset of the elements with the property that all other elements can be written as a linear combination of basis elements. Every basis of a finite-dimensional space has the same number of elements, which equals the dimension of the space. In the case of the cycle space, a basis is a family of exactly ${\displaystyle m-n+c}$ Eulerian subgraphs, with the property that every Eulerian subgraph can be written as the symmetric difference of a family of basis elements.

Existence

By Veblen's theorem, ^[11] every Eulerian subgraph of a given graph can be decomposed into simple cycles, subgraphs in which all vertices have degree zero or two and in which the degree-two vertices form a connected set. Therefore, it is always possible to find a basis in which the basis elements are themselves all simple cycles. Such a basis is called a cycle basis of the given graph. More strongly, it is always possible to find a basis in which the basis elements are induced cycles or even (in a 3-vertex-connected graph) non-separating induced cycles. ^[12]

Fundamental and weakly fundamental bases

One way of constructing a cycle basis is to form a maximal forest of the graph, and then for each edge ${\displaystyle e}$ that does not belong to the forest, form a cycle ${\displaystyle C_{e}}$ consisting of ${\displaystyle e}$ together with the path in the forest connecting the endpoints of ${\displaystyle e}$. The cycles ${\displaystyle C_{e}}$ formed in this way are linearly independent (each one contains an edge ${\displaystyle e}$ that does not belong to any of the other cycles) and has the correct size ${\displaystyle m-n+c}$ to be a basis, so it necessarily is a basis. A basis formed in this way is called a fundamental cycle basis (with respect to the chosen forest). ^[1]

If there exists a linear ordering of the cycles in a cycle basis such that each cycle includes at least one edge that is not part of any previous cycle, then the cycle basis is called weakly fundamental. Every fundamental cycle basis is weakly fundamental (for all linear orderings) but not necessarily vice versa. There exist graphs, and cycle bases for those graphs, that are not weakly fundamental. ^[13]

Minimum weight bases

If the edges of a graph are given real number weights, the weight of a subgraph may be computed as the sum of the weights of its edges. The minimum weight basis of the cycle space is necessarily a cycle basis, and can be constructed in polynomial time. ^[8] The minimum weight basis is not always weakly fundamental, and when it is not it is NP-hard to find the weakly fundamental basis with the minimum possible weight. ^[13]

Planar graphs

Homology

If a planar graph is embedded into the plane, its chain complex of edges and vertices may be embedded into a higher dimensional chain complex that also includes the sets of faces of the graph. The boundary map of this chain complex takes any 2-chain (a set of faces) to the set of edges that belong to an odd number of faces in the 2-chain. The boundary of a 2-chain is necessarily an Eulerian subgraph, and every Eulerian subgraph can be generated in this way from exactly two different 2-chains (each of which is the complement of the other). ^[14] It follows from this that the set of bounded faces of the embedding forms a cycle basis for the planar graph: removing the unbounded face from this set of cycles reduces the number of ways each Eulerian subgraph can be generated from two to exactly one.

Mac Lane's planarity criterion

Main article: Mac Lane's planarity criterion

Mac Lane's planarity criterion, named after Saunders Mac Lane, characterizes planar graphs in terms of their cycle spaces and cycle bases. It states that a finite undirected graph is planar if and only if the graph has a cycle basis in which each edge of the graph participates in at most two basis cycles. In a planar graph, a cycle basis formed by the set of bounded faces of an embedding necessarily has this property: each edge participates only in the basis cycles for the two faces it separates. Conversely, if a cycle basis has at most two cycles per edge, then its cycles can be used as the set of bounded faces of a planar embedding of its graph. ^{[14] [15]}

Duality

The cycle space of a planar graph is the cut space of its dual graph, and vice versa. The minimum weight cycle basis for a planar graph is not necessarily the same as the basis formed by its bounded faces: it can include cycles that are not faces, and some faces may not be included as cycles in the minimum weight cycle basis. There exists a minimum weight cycle basis in which no two cycles cross each other: for every two cycles in the basis, either the cycles enclose disjoint subsets of the bounded faces, or one of the two cycles encloses the other one. Following the duality between cycle spaces and cut spaces, this basis for a planar graph corresponds to a Gomory–Hu tree of the dual graph, a minimum weight basis for its cut space. ^[16]

Nowhere-zero flows

In planar graphs, colorings with ${\displaystyle k}$ distinct colors are dual to nowhere-zero flows over the ring ${\displaystyle \mathbb {Z} _{k}}$ of integers modulo ${\displaystyle k}$. In this duality, the difference between the colors of two adjacent regions is represented by a flow value across the edge separating the regions. In particular, the existence of nowhere-zero 4-flows is equivalent to the four color theorem. The snark theorem generalizes this result to nonplanar graphs. ^[17]

References

1. Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN   9781584885054 .
2. Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.
3. Joshi, K. D. (1997), Applied Discrete Structures, New Age International, p. 172, ISBN   9788122408263 .
4. Wallis, W. D. (2010), A Beginner's Guide to Graph Theory, Springer, p. 66, ISBN   9780817645809 .
5. Eppstein, David (1996), On the Parity of Graph Spanning Tree Numbers (PDF), Technical Report 96-14, Department of Information and Computer Science, University of California, Irvine.
6. Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23, ISBN   9783540442370 .
7. Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, p. 154, ISBN   9780521458979 .
8. Berger, Franziska; Gritzmann, Peter; de Vries, Sven (2009), "Minimum cycle bases and their applications", Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, vol. 5515, pp. 34–49, doi:10.1007/978-3-642-02094-0_2, ISBN   978-3-642-02093-3 .
9. Seymour, P. D. (1995), "Nowhere-zero flows", Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 289–299, MR   1373660 .
10. Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27–30, ISBN   9780486419756 .
11. Veblen, Oswald (1912), "An application of modular equations in analysis situs", Annals of Mathematics , Second Series, 14 (1): 86–94, doi:10.2307/1967604, JSTOR   1967604 .
12. Diestel (2012), pp. 32, 65.
13. Rizzi, Romeo (2009), "Minimum weakly fundamental cycle bases are hard to find", Algorithmica, 53 (3): 402–424, doi:10.1007/s00453-007-9112-8, MR   2482112 .
14. Diestel (2012), pp. 105–106.
15. Mac Lane, S. (1937), "A combinatorial condition for planar graphs" (PDF), Fundamenta Mathematicae, 28: 22–32.
16. Hartvigsen, David; Mardon, Russell (1994), "The all-pairs min cut problem and the minimum cycle basis problem on planar graphs", SIAM Journal on Discrete Mathematics, 7 (3): 403–418, doi:10.1137/S0895480190177042, MR   1285579 .
17. Thomas, Robin (1999), "Recent Excluded Minor Theorems for Graphs", Surveys in Combinatorics, 1999 (PDF), Cambridge University Press, pp. 201–222