Editing Cyclomatic number (section)

==Applications==
===Meshedness coefficient===
A variant of the cyclomatic number for [[planar graph]]s, normalized by dividing by the maximum possible cyclomatic number of any planar graph with the same vertex set, is called the [[meshedness coefficient]]. For a connected planar graph with {{mvar|m}} edges and {{mvar|n}} vertices, the meshedness coefficient can be computed by the formula<ref>{{citation
 | last1 = Buhl | first1 = J.
 | last2 = Gautrais | first2 = J.
 | last3 = Sole | first3 = R.V.
 | last4 = Kuntz | first4 = P.
 | last5 = Valverde | first5 = S.
 | last6 = Deneubourg | first6 = J.L.
 | last7 = Theraulaz | first7 = G.
 | doi = 10.1140/epjb/e2004-00364-9
 | issue = 1
 | journal = The European Physical Journal B
 | pages = 123–129
 | publisher = Springer-Verlag
 | title = Efficiency and robustness in ant networks of galleries
 | volume = 42
 | year = 2004| bibcode = 2004EPJB...42..123B
 }}.</ref>
:<math>\frac{m-n+1}{2n-5}.</math>
Here, the numerator <math>m-n+1</math> of the formula is the cyclomatic number of the given graph, and the denominator <math>2n-5</math> is the largest possible cyclomatic number of an {{mvar|n}}-vertex planar graph. The meshedness coefficient ranges between 0 for trees and 1 for [[maximal planar graph]]s.

===Ear decomposition===
The cyclomatic number 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 [[k-vertex-connected graph|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 <math>r</math>, every open ear decomposition has exactly <math>r</math> ears.<ref>{{citation
 | last = Whitney | first = H. | authorlink = Hassler Whitney
 | journal = [[Transactions of the American Mathematical Society]]
 | pages = 339–362
 | title = Non-separable and planar graphs
 | volume = 34
 | year = 1932
 | issue = 2 | doi=10.2307/1989545 | jstor = 1989545 | pmid = 16587624 | doi-access = free
 | pmc = 1076008
 }}. See in particular Theorems 18 (relating ear decomposition to circuit rank) and 19 (on the existence of ear decompositions).</ref>

===Almost-trees===
A graph with cyclomatic number <math>r</math> is also called an {{mvar|r}}''-almost-tree'', because only {{mvar|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'', and a connected near-tree is a [[pseudoforest|pseudotree]], a cycle with a (possibly trivial) tree rooted at each vertex.<ref name=CMC349>{{citation | last=Brualdi | first=Richard A. | title=Combinatorial Matrix Classes | series=Encyclopedia of Mathematics and Its Applications | volume=108 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2006 | isbn=0-521-86565-4 | zbl=1106.05001 | page=[https://archive.org/details/combinatorialmat0000brua/page/349 349] | url=https://archive.org/details/combinatorialmat0000brua/page/349 }}</ref>

Several authors have studied the [[parameterized complexity]] of graph algorithms on {{mvar|r}}-near-trees, parameterized by <math>r</math>.<ref>{{citation
 | last1 = Coppersmith | first1 = Don | author1-link = Don Coppersmith
 | last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin
 | doi = 10.1016/0166-218X(85)90057-5 | zbl=0573.68017
 | issue = 1
 | journal = Discrete Applied Mathematics
 | pages = 27–45
 | title = Solving NP-hard problems in 'almost trees': Vertex cover
 | volume = 10
 | year = 1985| doi-access = free
 }}.</ref><ref>{{citation
 | last1 = Fiala | first1 = Jiří
 | last2 = Kloks | first2 = Ton
 | last3 = Kratochvíl | first3 = Jan
 | doi = 10.1016/S0166-218X(00)00387-5 | zbl=0982.05085
 | issue = 1
 | journal = Discrete Applied Mathematics
 | pages = 59–72
 | title = Fixed-parameter complexity of λ-labelings
 | volume = 113
 | year = 2001| doi-access = free
 }}.</ref>

===Generalizations to directed graphs===
The [[cycle rank]] is an invariant of [[directed graph]]s that measures the level of nesting of cycles in the graph. It has a more complicated definition than cyclomatic number (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 cyclomatic number 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===
In the fields of [[chemistry]] and [[cheminformatics]], the cyclomatic number of a [[molecular graph]] (the number of [[ring (chemistry)|rings]] in the [[smallest set of smallest rings]]) is sometimes referred to as the '''Frèrejacque number'''.<ref>{{citation|last1=May|first1=John W.|last2=Steinbeck|first2=Christoph|title=Efficient ring perception for the Chemistry Development Kit|journal=[[Journal of Cheminformatics]]|volume=6|issue=3|year=2014|page=3 |doi=10.1186/1758-2946-6-3|pmid=24479757|pmc=3922685 |doi-access=free }}</ref><ref>{{citation|last1=Downs|first1=G.M.|last2=Gillet|first2=V.J.|last3=Holliday|first3=J.D.|last4=Lynch|first4=M.F.|year=1989|title=A review of ''Ring Perception Algorithms for Chemical Graphs''|journal=[[J. Chem. Inf. Comput. Sci.]]|volume=29|issue=3|pages=172–187|doi=10.1021/ci00063a007}}</ref><ref>{{citation|first1=Marcel|last1=Frèrejacque|title=No. 108-Condensation d'une molecule organique|trans-title=Condensation of an organic molecule|journal=[[Bull. Soc. Chim. Fr.]]|volume=5|pages=1008–1011|year=1939}}</ref>

=== Parametrized complexity ===
Some computational problems on graphs are NP-hard in general, but can be solved in [[polynomial time]] for graphs with a small cyclomatic number. An example is the path reconfiguration problem.<ref>{{citation | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine | last2 = Eppstein | first2 = David | author2-link = David Eppstein | last3 = Hesterberg | first3 = Adam | last4 = Jain | first4 = Kshitij | last5 = Lubiw | first5 = Anna | author5-link = Anna Lubiw | last6 = Uehara | first6 = Ryuhei | last7 = Uno | first7 = Yushi | editor1-last = Friggstad | editor1-first = Zachary | editor2-last = Sack | editor2-first = Jörg-Rüdiger | editor2-link = Jörg-Rüdiger Sack | editor3-last = Salavatipour | editor3-first = Mohammad R. | arxiv = 1905.00518 | contribution = Reconfiguring Undirected Paths | doi = 10.1007/978-3-030-24766-9_26 | pages = 353–365 | publisher = Springer | series = Lecture Notes in Computer Science | title = Algorithms and Data Structures – 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings | title-link = SWAT and WADS conferences | volume = 11646 | isbn = 978-3-030-24765-2 | year = 2019}}</ref>