To listout the cycles maybe this can help
http://comeoncodeon.wordpress.com/2010/06/07/number-of-cycles-in-a-graph/
Note that the number of simple cycles in a graph with n nodes can be exponential in n.
The above link has an algorithm to find all cycles . Do you have a formula to find exact number of simple cycles in a graph?
Do you want all the cycles or all the simple cycles which is a very different problem ?
The problem I see is that if we consider a complete graph then all simple cycles corresponds to the enumeration of all the parts of a set since you can create a simple cycle with all the combinations of vertices. The size of the set of parts is exponential to the number of elements. Secondly, you seem to ask for a formula but I don't see how you can exhibit a formula without actually operating an an algorithm. Your formula would obviously depend on the shape of the graph and some additional hypothesis like do you allow or not multiple arcs between the same nods.
Would not the formula for the number of simple cycles in a graph be limited to, solely dependent upon, and determined by -- thus not NP Complete -- the smallest angle (Eric Andres' "shape of the graph") within and among the nodes of each simple (closed) cycle, before then summing those cycles?
Friends, There is a formula to find number of circuit vectors in a vector space of graph G (planar or nonplanar). But this circuit subspace contains disjoint union of cycles also . I could not separate simple cycles easily. why can not we separate them by a formula?.Is it not possible ,?
Dear Nev , the above link gives different algorithm to find path and cycles. iam looking for formula to separate all simple cycles from a Circuit Subspace of a vector space of a Graph.
Counting simple cycles in a graph is NP-hard. See, e.g., Claim 1 in these lecture notes of J. Katz: http://www.cs.umd.edu/~jkatz/complexity/f11/lecture23.pdf
(the Claim deals with directed graphs, but the argument can be easily adapted to undirected graphs as well).
You need to give additional details about your problem. If you know adjacency matrix of your graph and want to count number of simple cycles of fixed length look at slides and papers in my profile.
Sergey Perepechko
The paper mentioned above by S. Aref provides an algorithm for finding the simple cycles and simple paths, not an analytical formula. For this I recommend you look at Prof. Perepechko slides as well as http://arxiv.org/abs/1606.00289 where explicit analytical formulas are provided for both simple cycles and simple paths. The paper also contains Prof. Perepechko's formula.
I should add that general purpose Matlab algorithms for counting simple cycles and simple paths a.k.a. self-avoiding polygons and self-avoiding walks are available on the File Exchange
https://uk.mathworks.com/matlabcentral/fileexchange/60814
https://uk.mathworks.com/matlabcentral/fileexchange/63850
https://uk.mathworks.com/matlabcentral/fileexchange/63849
An in-depth analysis of these algorithms is available at Article A General Purpose Algorithm for Counting Simple Cycles and S...
It will soon appear in Algorithmica.
- Badges
- Science topic