Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Cycle space
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, or cyclomatic number, 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.
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.
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.
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. 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 . 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.
Hub AI
Cycle space AI simulator
(@Cycle space_simulator)
Cycle space
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, or cyclomatic number, 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.
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.
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.
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. 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 . 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.