Circuit rank

From Wikipedia, the free encyclopedia

In graph-theoretic mathematics, the circuit rank, cyclomatic number, or nullity of an undirected graph G is the minimum number r of edges to remove from G 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

r=m-n+c,

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

Related concepts

The circuit rank is the corank of the graphic matroid of G,[2] 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 r edges the removal of which leaves G acyclic. Alternatively, such a set may be found as the complement of a spanning forest of G.

The cyclomatic number is also the dimension of the cycle space of G.[1] Topologically, G 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,[3]

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

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

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 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.[5]

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

See also

References

  1. ↑ 1.0 1.1 Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27–30, ISBN 9780486419756 .
  2. ↑ Berge, Claude (1976), Graphs and Hypergraphs, North-Holland Mathematical Library 6, Elsevier, p. 477, ISBN 9780720424539 .
  3. ↑ Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23 .
  4. ↑ Whitney, H. (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society 34: 339–362 . See in particular Theorems 18 (relating ear decomposition to circuit rank) and 19 (on the existence of ear decompositions).
  5. ↑ Brualdi, Richard A. (2006), Combinatorial matrix classes, Encyclopedia of Mathematics and Its Applications 108, Cambridge: Cambridge University Press, p. 349, ISBN 0-521-86565-4, Zbl 1106.05001 
  6. ↑ 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 .
  7. ↑ 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 .
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.