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 (the size of a cycle basis). Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula
- ,
where m is the number of edges in the given graph, n is the number of vertices, and c is the number of connected components. [1] It is also possible to construct a minimum-size set of edges that breaks all cycles efficiently, either using a greedy algorithm or by complementing a spanning forest.
The circuit rank can be explained in terms of algebraic graph theory as the dimension of the cycle space of a graph, in terms of matroid theory as the corank of a graphic matroid, and in terms of topology as one of the Betti numbers of a topological space derived from the graph. It counts the ears in an ear decomposition of the graph, forms the basis of parameterized complexity on almost-trees, and has been applied in software metrics as part of the definition of cyclomatic complexity of a piece of code. Under the name of cyclomatic number, the concept was introduced by Gustav Kirchhoff.[2][3]
- ^ Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27–30, ISBN 9780486419756.
- ^ Peter Robert Kotiuga (2010), A Celebration of the Mathematical Legacy of Raoul Bott, American Mathematical Soc., p. 20, ISBN 978-0-8218-8381-5
- ^ Per Hage (1996), Island Networks: Communication, Kinship, and Classification Structures in Oceania, Cambridge University Press, p. 48, ISBN 978-0-521-55232-5