Circuit rank

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

r=m-n+c

,

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]

Matroid rank and construction of a minimum feedback edge set[edit]

The circuit rank of a graph $G$ may be described using matroid theory as the corank of the graphic matroid of $G$ .^[4] Using the greedy property of matroids, this means that one can find a minimum set of edges that breaks all cycles using a greedy algorithm that at each step chooses an edge that belongs to at least one cycle of the remaining graph.

Alternatively, a minimum set of edges that breaks all cycles can be found by constructing a spanning forest of $G$ and choosing the complementary set of edges that do not belong to the spanning forest.

The number of independent cycles[edit]

In algebraic graph theory, the circuit rank is also the dimension of the cycle space of $G$ . 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 homology theory, a branch of topology. Any graph $G$ may be viewed as an example of a 1-dimensional simplicial complex, a type of topological space formed by representing each graph edge by a line segment and gluing these line segments together at their endpoints. The cyclomatic number is the rank of the first (integer) homology group of this complex,^[5]

r=\operatorname {rank} \left[H_{1}(G,\mathbb {Z} )\right].

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[edit]

Meshedness coefficient[edit]

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]

{\frac {m-n+1}{2n-5}}.

Here, the numerator $m-n+1$ of the formula is the circuit rank of the given graph, and the denominator $2n-5$ is the largest possible circuit rank of an $n$ -vertex planar graph. The meshedness coefficient ranges between 0 for trees and 1 for maximal planar graphs.

Ear decomposition[edit]

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 $r$ , every open ear decomposition has exactly $r$ ears.^[8]

Almost-trees[edit]

A graph with cyclomatic number $r$ 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 $r$ .^[10]^[11]

Generalizations to directed graphs[edit]

The cycle rank is an invariant of directed graphs that measures the level of nesting of cycles in the graph. It has a more complicated definition than circuit rank (closely related to the definition of tree-depth for undirected graphs) and is more difficult to compute. Another problem for directed graphs related to the circuit rank is the minimum feedback arc set, the smallest set of edges whose removal breaks all directed cycles. Both cycle rank and the minimum feedback arc set are NP-hard to compute.

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[edit]

In the fields of chemistry and cheminformatics, the circuit rank of a molecular graph (the number of rings in the smallest set of smallest rings) is sometimes referred to as the Frèrejacque number.^[12]^[13]^[14]

Parametrized complexity[edit]

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[edit]

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[edit]

^ ^a ^b 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
^ Berge, Claude (1976), Graphs and Hypergraphs, North-Holland Mathematical Library, vol. 6, Elsevier, p. 477, ISBN 9780720424539.
^ Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23, ISBN 9783540442370.
^ Gregory Berkolaiko; Peter Kuchment (2013), Introduction to Quantum Graphs, American Mathematical Soc., p. 4, ISBN 978-0-8218-9211-4
^ Buhl, J.; Gautrais, J.; Sole, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (2004), "Efficiency and robustness in ant networks of galleries", The European Physical Journal B, 42 (1), Springer-Verlag: 123–129, doi:10.1140/epjb/e2004-00364-9.
^ Whitney, H. (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society, 34 (2): 339–362, doi:10.2307/1989545, JSTOR 1989545, PMC 1076008, PMID 16587624. See in particular Theorems 18 (relating ear decomposition to circuit rank) and 19 (on the existence of ear decompositions).
^ Brualdi, Richard A. (2006), Combinatorial Matrix Classes, Encyclopedia of Mathematics and Its Applications, vol. 108, Cambridge: Cambridge University Press, p. 349, ISBN 0-521-86565-4, Zbl 1106.05001
^ Coppersmith, Don; Vishkin, Uzi (1985), "Solving NP-hard problems in 'almost trees': Vertex cover", Discrete Applied Mathematics, 10 (1): 27–45, doi:10.1016/0166-218X(85)90057-5, Zbl 0573.68017.
^ Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan (2001), "Fixed-parameter complexity of λ-labelings", Discrete Applied Mathematics, 113 (1): 59–72, doi:10.1016/S0166-218X(00)00387-5, Zbl 0982.05085.
^ May, John W.; Steinbeck, Christoph (2014), "Efficient ring perception for the Chemistry Development Kit", Journal of Cheminformatics, 6 (3): 3, doi:10.1186/1758-2946-6-3, PMC 3922685, PMID 24479757
^ Downs, G.M.; Gillet, V.J.; Holliday, J.D.; Lynch, M.F. (1989), "A review of Ring Perception Algorithms for Chemical Graphs", J. Chem. Inf. Comput. Sci., 29 (3): 172–187, doi:10.1021/ci00063a007
^ Frèrejacque, Marcel (1939), "No. 108-Condensation d'une molecule organique" [Condenstation of an organic molecule], Bull. Soc. Chim. Fr., 5: 1008–1011
^ Demaine, Erik D.; Eppstein, David; Hesterberg, Adam; Jain, Kshitij; Lubiw, Anna; Uehara, Ryuhei; Uno, Yushi (2019), "Reconfiguring Undirected Paths", in Friggstad, Zachary; Sack, Jörg-Rüdiger; Salavatipour, Mohammad R. (eds.), Algorithms and Data Structures – 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11646, Springer, pp. 353–365, arXiv:1905.00518, doi:10.1007/978-3-030-24766-9_26, ISBN 978-3-030-24765-2

[berge-1] Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27–30, ISBN 9780486419756.

[Kotiuga2010-2] Peter Robert Kotiuga (2010), A Celebration of the Mathematical Legacy of Raoul Bott, American Mathematical Soc., p. 20, ISBN 978-0-8218-8381-5

[Hage1996-3] Per Hage (1996), Island Networks: Communication, Kinship, and Classification Structures in Oceania, Cambridge University Press, p. 48, ISBN 978-0-521-55232-5

[4] Berge, Claude (1976), Graphs and Hypergraphs, North-Holland Mathematical Library, vol. 6, Elsevier, p. 477, ISBN 9780720424539.

[5] Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23, ISBN 9783540442370.

[BerkolaikoKuchment2013-6] Gregory Berkolaiko; Peter Kuchment (2013), Introduction to Quantum Graphs, American Mathematical Soc., p. 4, ISBN 978-0-8218-9211-4

[7] Buhl, J.; Gautrais, J.; Sole, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (2004), "Efficiency and robustness in ant networks of galleries", The European Physical Journal B, 42 (1), Springer-Verlag: 123–129, doi:10.1140/epjb/e2004-00364-9.

[8] Whitney, H. (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society, 34 (2): 339–362, doi:10.2307/1989545, JSTOR 1989545, PMC 1076008, PMID 16587624. See in particular Theorems 18 (relating ear decomposition to circuit rank) and 19 (on the existence of ear decompositions).

[CMC349-9] Brualdi, Richard A. (2006), Combinatorial Matrix Classes, Encyclopedia of Mathematics and Its Applications, vol. 108, Cambridge: Cambridge University Press, p. 349, ISBN 0-521-86565-4, Zbl 1106.05001

[10] Coppersmith, Don; Vishkin, Uzi (1985), "Solving NP-hard problems in 'almost trees': Vertex cover", Discrete Applied Mathematics, 10 (1): 27–45, doi:10.1016/0166-218X(85)90057-5, Zbl 0573.68017.

[11] Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan (2001), "Fixed-parameter complexity of λ-labelings", Discrete Applied Mathematics, 113 (1): 59–72, doi:10.1016/S0166-218X(00)00387-5, Zbl 0982.05085.

[12] May, John W.; Steinbeck, Christoph (2014), "Efficient ring perception for the Chemistry Development Kit", Journal of Cheminformatics, 6 (3): 3, doi:10.1186/1758-2946-6-3, PMC 3922685, PMID 24479757

[13] Downs, G.M.; Gillet, V.J.; Holliday, J.D.; Lynch, M.F. (1989), "A review of Ring Perception Algorithms for Chemical Graphs", J. Chem. Inf. Comput. Sci., 29 (3): 172–187, doi:10.1021/ci00063a007

[14] Frèrejacque, Marcel (1939), "No. 108-Condensation d'une molecule organique" [Condenstation of an organic molecule], Bull. Soc. Chim. Fr., 5: 1008–1011

[15] Demaine, Erik D.; Eppstein, David; Hesterberg, Adam; Jain, Kshitij; Lubiw, Anna; Uehara, Ryuhei; Uno, Yushi (2019), "Reconfiguring Undirected Paths", in Friggstad, Zachary; Sack, Jörg-Rüdiger; Salavatipour, Mohammad R. (eds.), Algorithms and Data Structures – 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11646, Springer, pp. 353–365, arXiv:1905.00518, doi:10.1007/978-3-030-24766-9_26, ISBN 978-3-030-24765-2

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]