graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a branch of

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, the circuit rank, cyclomatic number, cycle rank, or nullity of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

or forest. It is equal to the number of independent cycles in the graph (the size of a

cycle basis In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be exp ...

). Unlike the corresponding

feedback arc set In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks al ...

problem for

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

s, the circuit rank is easily computed using the formula :

r = m - n + c

, where is the number of edges in the given graph, is the number of vertices, and is the number of connected components. . It is also possible to construct a minimum-size set of edges that breaks all cycles efficiently, either using a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

or by complementing a

spanning forest In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

. The circuit rank can be explained in terms of

algebraic graph theory Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph t ...

as the dimension of the

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 dime ...

of a graph, in terms of

matroid theory In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in ...

as the corank of a

graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co- ...

, and in terms of

topology In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...

as one of the

Betti number In algebraic topology, the Betti numbers are used to distinguish topological spaces based on the connectivity of ''n''-dimensional simplicial complexes. For the most reasonable finite-dimensional spaces (such as compact manifolds, finite simplicia ...

s of a topological space derived from the graph. It counts the ears in an

ear decomposition In graph theory, an ear of an undirected graph ''G'' is a path ''P'' where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of ''P'' has degree two in ''G''. An ...

of the graph, forms the basis of

parameterized complexity In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

on almost-trees, and has been applied in

software metric In software engineering and development, a software metric is a standard of measure of a degree to which a software system or process possesses some property. Even if a metric is not a measurement (metrics are functions, while measurements are t ...

s as part of the definition of

cyclomatic complexity Cyclomatic complexity is a software metric used to indicate the complexity of a program. It is a quantitative measure of the number of linearly independent paths through a program's source code. It was developed by Thomas J. McCabe, Sr. in 1976 ...

of a piece of code. Under the name of cyclomatic number, the concept was introduced by

Gustav Kirchhoff Gustav Robert Kirchhoff (; 12 March 1824 – 17 October 1887) was a German physicist who contributed to the fundamental understanding of electrical circuits, spectroscopy, and the emission of black-body radiation by heated objects. He coine ...

Matroid rank and construction of a minimum feedback edge set

The circuit rank of a graph may be described using

as the corank of the

of . Using the greedy property of matroids, this means that one can find a minimum set of edges that breaks all cycles using a

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

of and choosing the

complementary A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...

set of edges that do not belong to the spanning forest.

The number of independent cycles

, the circuit rank is also the dimension of the

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 In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. Th ...

of some subset of the others. This count of independent cycles can also be explained using

homology theory In mathematics, homology is a general way of associating a sequence of algebraic objects, such as abelian groups or modules, with other mathematical objects such as topological spaces. Homology groups were originally defined in algebraic topolog ...

, a branch of

. Any graph may be viewed as an example of a 1-dimensional

simplicial complex In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial set ...

, a type of

topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...

formed by representing each graph edge by a

line segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...

and gluing these line segments together at their endpoints. The cyclomatic number is the

rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * H ...

of the first (integer)

homology group In mathematics, homology is a general way of associating a sequence of algebraic objects, such as abelian groups or modules, with other mathematical objects such as topological spaces. Homology groups were originally defined in algebraic topolog ...

of this complex, :

r = \operatorname\left_1(G,\Z)\right

Because of this topological connection, the cyclomatic number of a graph is also called the first

of . 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 graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s, 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 edges and vertices, the meshedness coefficient can be computed by the formula :

\frac.

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 -vertex planar graph. The meshedness coefficient ranges between 0 for trees and 1 for

maximal planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

Ear decomposition

The circuit rank controls the number of ears in an

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.

Almost-trees

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. Several authors have studied the

of graph algorithms on ''r''-near-trees, parameterized by

r

Generalizations to directed graphs

The

cycle rank In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a DAG has ...

is an invariant of

s 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 In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. This invariant and its close relatives have gone under many different names in the lite ...

for undirected graphs) and is more difficult to compute. Another problem for directed graphs related to the circuit rank is the minimum

, the smallest set of edges whose removal breaks all directed cycles. Both cycle rank and the minimum feedback arc set are

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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

, a software metric for estimating how complicated a piece of computer code is.

Computational chemistry

In the fields of

chemistry Chemistry is the science, scientific study of the properties and behavior of matter. It is a natural science that covers the Chemical element, elements that make up matter to the chemical compound, compounds made of atoms, molecules and ions ...

and

cheminformatics Cheminformatics (also known as chemoinformatics) refers to use of physical chemistry theory with computer and information science techniques—so called "''in silico''" techniques—in application to a range of descriptive and prescriptive problem ...

, the circuit rank of a

molecular graph In chemical graph theory and in mathematical chemistry, a molecular graph or chemical graph is a representation of the structural formula of a chemical compound in terms of graph theory. A chemical graph is a labeled graph whose vertices corresp ...

(the number of

rings Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...

in the

smallest set of smallest rings In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expr ...

) is sometimes referred to as the Frèrejacque number.

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.

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 In graph theory, a branch of mathematics, the matching preclusion number of a graph ''G'' (denoted mp(''G'')) is the minimum number of edges whose deletion results in the destruction of a perfect matching or near-perfect matching (a matching that c ...

- the minimum number of edges to delete in order to prevent the existence of a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

; *

Feedback vertex set In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles ("removal" means deleting the vertex and all edges adjacent to it). Equivalently, each FVS conta ...

number - the minimum number of vertices to delete in order to make the graph acyclic; *

Feedback arc set In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks al ...

- the minimum number of arcs to delete from a directed graph, in order to make it acyclic.

References

{{reflist Graph invariants Matroid theory Spanning tree