Talk:Circuit rank

is there proof that the algorithm which is provided here does not fall into local optima? just because its greedy does not means it returns a globally optimal solution...

You are right that greediness is very far from a guarantee of global optimality, indeed it generally serves better as a suggestive indicator of non-optimality. But in this case, the greediness of the algorithm is irrelevant. The only thing that's going on in this proof is a comparison of the number of edges in the original graph to the number of edges in any forest with the same number of components and the same number of vertices. That's what establishes that the circuit rank is a well-defined property of the graph. The fact that the choice of edges to delete may be made arbitrarily follows immediately from the fact that all such forests have the same number of edges. And that's what ensures that the greedy algorithm for deleting edges suffices.—PaulTanenbaum (talk) 21:27, 14 September 2011 (UTC)[reply]

Could use an extensive re-write

I grasp that one of the primary people to whom this is of interest are mathematicians, and I've got enough of a math background that I'm sure I could get an understanding of this, but there are lots of people to whom Cyclomatic Complexity (which maps to this page) is of interest who are not themselves mathematically oriented and don't want to spend a lot of time developing an understanding of otherwise limited-use deep mathematical jargon to get a handle on this concept... namely, computer people. This article could use a much more jargon-limited summary, perhaps with some simple examples pertaining to computational usage and a few graphics showing basic examples.
If that's objectionable, then the article should be forked into this one and one titled "cyclomatic complexity" which is designed to be read by non-mathematicians. I am willing to bet that the basic elements of this notion could be gotten across without 15 side forays into specialist terminology just to have an essential feel for what the term means.
--216.52.207.72 (talk) 21:48, 14 July 2015 (UTC)[reply]

I've expanded the article in a way that I hope makes the technical parts easier to follow. But in what sense is the lead section of the article not already the "jargon-limited summary" you ask for? You don't have to read the more technical parts about matroids etc. if you don't want to. —David Eppstein (talk) 22:02, 14 July 2015 (UTC)[reply]

m edges and n edges

In fragment For a connected planar graph with m edges and n edges n must be nodes, not edges, Jumpow (talk) 16:24, 3 August 2016 (UTC)[reply]

Terminology

The term "circuit rank" is not common in graph theory, as far as I have seen in years of reading. A more common name is "cycle rank". The names "cyclomatic number" and "nullity" have also been used often enough. I would place those names in the first sentence. (Was this article written by a computer scientist? They have their own terminology for graph theory.) Zaslav (talk) 08:30, 22 August 2016 (UTC)[reply]

Google scholar says it's the term used by Ore's 1962 text Theory of Graphs, by Whitney's 1935 "On the abstract properties of linear dependence", and by Harary and Walsh's 1969 "Matroids versus graphs", among others, so it seems intrinsic to graph theory and matroid theory rather than being a neologism from CS. Part of the issue is that cycle rank also means something else, for directed graphs. Google scholar also says that this term is far less used than "cyclomatic number", though, which would be my preference (because it is colorful and unambiguous, as well as appearing in the literature 3x more than cycle rank and 15x more than circuit rank). —David Eppstein (talk) 06:00, 24 August 2016 (UTC)[reply]

The references mentioned by David Eppstein are quite old (≥ 48 years). I don't believe the term "circuit rank" has been used much in graph or matroid theory for many years, since it feels wrong to me based on my reading of graph theory "as she is spoke". "Cycle rank" is most common in graph theory, I believe. (I prefer "cyclomatic number" but I seem to be in a minority.) I recommend changing the title to "Cycle rank" to conform with usage of the past few decades. Can others give their observations? Zaslav (talk) 04:28, 10 September 2017 (UTC)[reply]

P.S. I would heartily support the title "Cyclomatic number". If David Eppstein is right about the frequency of usage, it is clearly best. I'm not sure how much we should rely on Google Scholar for such data. Is there evidence about that? Zaslav (talk) 01:28, 13 September 2017 (UTC)[reply]

Circuit rank as a basis for software cyclomatic complexity

The article states:

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

Is this an original observation of the contributor? If so, could the author please explain further? Is this substantiated by other published research? Please provide citations if so. Atester (talk) 18:17, 11 June 2019 (UTC)[reply]

Euler

Isn't this simply the Euler characteristic? 5.28.186.92 (talk) 15:03, 24 November 2022 (UTC)[reply]