Circuit rank
In
- ,
where m is the number of edges in the given graph, n is the number of
The circuit rank can be explained in terms of
Matroid rank and construction of a minimum feedback edge set
The circuit rank of a graph G may be described using
Alternatively, a minimum set of edges that breaks all cycles can be found by constructing a
The number of independent cycles
In algebraic graph theory, the circuit rank is also the dimension of the cycle space of . Intuitively, this can be explained as meaning that the circuit rank counts the number of independent cycles in the graph, where a collection of cycles is independent if it is not possible to form one of the cycles as the symmetric difference of some subset of the others.[1]
This count of independent cycles can also be explained using
Because of this topological connection, the cyclomatic number of a graph G is also called the first Betti number of G.[6] More generally, the first Betti number of any topological space, defined in the same way, counts the number of independent cycles in the space.
Applications
Meshedness coefficient
A variant of the circuit rank for planar graphs, normalized by dividing by the maximum possible circuit rank of any planar graph with the same vertex set, is called the meshedness coefficient. For a connected planar graph with m edges and n vertices, the meshedness coefficient can be computed by the formula[7]
Here, the numerator of the formula is the circuit rank of the given graph, and the denominator is the largest possible circuit rank of an n-vertex planar graph. The meshedness coefficient ranges between 0 for trees and 1 for
Ear decomposition
The circuit rank controls the number of ears in an ear decomposition of a graph, a partition of the edges of the graph into paths and cycles that is useful in many graph algorithms. In particular, a graph is 2-vertex-connected if and only if it has an open ear decomposition. This is a sequence of subgraphs, where the first subgraph is a simple cycle, the remaining subgraphs are all simple paths, each path starts and ends on vertices that belong to previous subgraphs, and each internal vertex of a path appears for the first time in that path. In any biconnected graph with circuit rank , every open ear decomposition has exactly ears.[8]
Almost-trees
A graph with cyclomatic number is also called a r-almost-tree, because only r edges need to be removed from the graph to make it into a tree or forest. A 1-almost-tree is a near-tree: a connected near-tree is a pseudotree, a cycle with a (possibly trivial) tree rooted at each vertex.[9]
Several authors have studied the parameterized complexity of graph algorithms on r-near-trees, parameterized by .[10][11]
Generalizations to directed graphs
The
It is also possible to compute a simpler invariant of directed graphs by ignoring the directions of the edges and computing the circuit rank of the underlying undirected graph. This principle forms the basis of the definition of cyclomatic complexity, a software metric for estimating how complicated a piece of computer code is.
Computational chemistry
In the fields of
Parametrized complexity
Some computational problems on graphs are NP-hard in general, but can be solved in polynomial time for graphs with a small circuit rank. An example is the path reconfiguration problem.[15]
Related concepts
Other numbers defined in terms of deleting things from graphs are:
- Edge connectivity- the minimum number of edges to delete in order to disconnect the graph;
- Matching preclusion - the minimum number of edges to delete in order to prevent the existence of a perfect matching;
- Feedback vertex set number - the minimum number of vertices to delete in order to make the graph acyclic;
- Feedback arc set - the minimum number of arcs to delete from a directed graph, in order to make it acyclic.
References
- ^ ISBN 9780486419756.
- ISBN 978-0-8218-8381-5
- ISBN 978-0-521-55232-5
- ISBN 9780720424539.
- ISBN 9783540442370.
- ISBN 978-0-8218-9211-4
- .
- PMID 16587624. See in particular Theorems 18 (relating ear decomposition to circuit rank) and 19 (on the existence of ear decompositions).
- Zbl 1106.05001
- Zbl 0573.68017.
- Zbl 0982.05085.
- PMID 24479757
- Bull. Soc. Chim. Fr., 5: 1008–1011
- ISBN 978-3-030-24765-2