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.
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.
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 2m 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]
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 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 neighborhoods 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 . [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 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 of edges in a graph forms a cut if and only if every Eulerian subgraph has an even number of edges in common with , and forms an Eulerian subgraph if and only if every cut has an even number of edges in common with . [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 if and only if has an even number of spanning forests. [5]
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
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 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
It can be defined in graph theoretic terms by choosing an arbitrary orientation of the graph, and defining an integral cycle of a graph to be an assignment of integers to the edges of (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 or of (the cycle space modulo ) 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 -flow. [9]
As a vector space, the dimension of the cycle space of a graph with vertices, edges, and connected components is . [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 .
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 Eulerian subgraphs, with the property that every Eulerian subgraph can be written as the symmetric difference of a family of basis elements.
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]
One way of constructing a cycle basis is to form a maximal forest of the graph, and then for each edge that does not belong to the forest, form a cycle consisting of together with the path in the forest connecting the endpoints of . The cycles formed in this way are linearly independent (each one contains an edge that does not belong to any of the other cycles) and has the correct size 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]
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]
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, 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]
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]
In planar graphs, colorings with distinct colors are dual to nowhere-zero flows over the ring of integers modulo . 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]
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσοςisos "equal", and μορφήmorphe "form" or "shape".
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of edge set E, such that every vertex in the vertex set V is adjacent to exactly one edge in M.
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs.
In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.
In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.
In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.
In the mathematical discipline of graph theory, the edge space and vertex space of an undirected graph are vector spaces defined in terms of the edge and vertex sets, respectively. These vector spaces make it possible to use techniques of linear algebra in studying the graph.
In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.
In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.
In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.
In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.
In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph , find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph.
In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles.
In geometry and crystallography, the Laves graph is an infinite and highly symmetric system of points and line segments in three-dimensional Euclidean space, forming a periodic graph. Three equal-length segments meet at 120° angles at each point, and all cycles use ten or more segments. It is the shortest possible triply periodic graph, relative to the volume of its fundamental domain. One arrangement of the Laves graph uses one out of every eight of the points in the integer lattice as its points, and connects all pairs of these points that are nearest neighbors, at distance . It can also be defined, divorced from its geometry, as an abstract undirected graph, a covering graph of the complete graph on four vertices.
In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.