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 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. 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. The circuit rank of a graph G may be described using matroid theory as the corank of the graphic matroid of G. 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. In algebraic graph theory, the circuit rank is also the dimension of the cycle space of .

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (19)

Related lectures (4)

Dual graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e.

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-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid (but this should not be confused with matroids of rank 3, which generalize planar point configurations); these are exactly the graphic matroids formed from planar graphs.

Circuit rank

Irreversible and Reversible Circuit Theorems CS-308: Quantum computation

Covers the proofs of Irreversible and Reversible circuit theorems, focusing on gates and the issue of irreversibility and reversibility.

Exchangeability and Network Statistics MATH-448: Statistical analysis of network data

Explores exchangeability, statistical summaries for networks, invariance issues, and the Poisson Limit theorem in network statistics.

Linear Algebra Basics MATH-213: Differential geometry

Covers the basics of linear algebra, including rank, differentiable applications, and submersions.