Circuit rank

From formulasearchengine
Jump to navigation Jump to search

In graph-theoretic mathematics, the circuit rank, cyclomatic number, or nullity of an undirected graph is the minimum number of edges to remove from to remove all its cycles, making it into a forest. Unlike the corresponding feedback arc set problem for directed graphs, it is easily computed, using the simple formula

,

where is the number of edges in , is the number of vertices, and is the number of connected components.[1]

Under the name of cyclomatic number, the concept was introduced by Gustav Kirchhoff.[2][3]

Related concepts

The circuit rank is the corank of the graphic matroid of ,[4] from which it can be seen that a greedy algorithm that removes edges one by one, at each step removing an edge that belongs to at least one cycle of the remaining graph, will necessarily find a set of edges the removal of which leaves acyclic. Alternatively, such a set may be found as the complement of a spanning forest of .

The cyclomatic number is also the dimension of the cycle space of .[1] Topologically, may be viewed as an example of a 1-dimensional simplicial complex, and its cyclomatic number is the rank of the first (integer) homology group of this complex,[5]

,

and because of this the cyclomatic number is also called the first Betti number.[6]

The circuit rank controls the number of ears in an ear decomposition of a graph: in a biconnected graph with circuit rank , every open ear decomposition has exactly ears.[7]

Other numbers defined in terms of edge deletion from undirected graphs include the edge connectivity, the minimum number of edges to delete in order to disconnect the graph, and matching preclusion, the minimum number of edges to delete in order to prevent the existence of a perfect matching.

Almost trees

A graph with cyclomatic number 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.[8]

Several authors have studied the parameterized complexity of graph algorithms on r-near-trees, parameterized by .[9][10]

See also

References

  1. 1.0 1.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  2. {{#invoke:citation/CS1|citation |CitationClass=book }}
  3. {{#invoke:citation/CS1|citation |CitationClass=book }}
  4. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  5. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  6. {{#invoke:citation/CS1|citation |CitationClass=book }}
  7. {{#invoke:citation/CS1|citation |CitationClass=citation }}. See in particular Theorems 18 (relating ear decomposition to circuit rank) and 19 (on the existence of ear decompositions).
  8. {{#invoke:citation/CS1|citation |CitationClass=citation }}
  9. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  10. {{#invoke:citation/CS1|citation |CitationClass=citation }}.