Finding all cycles in an undirected graph is an interesting problem. Few days ago, I tried to count all the cycles in a K6, a complete graph with 6 vertices. Finding the 7 cycles from a K4 is easy. But finding the 197 cycles in a K6 is not that trivial. Then I wrote a c++ code to enumerate all cycles in a graph. I tested it on some connected graphs and the results seem correct. Here are the results for the complete graphs, which I can verify by (sum_{k=3}^{n}{1/2 * nCr(n,k)*(k-1)!}.
Number of vertices, number of cycles
3, 1
4,7
5,37
6,197
7,1172
8,8018
9,62814
10,556014
11,5,488,059
20,174548332364311563
Here is the code: graph.txt allcycles.cpp
Thursday, February 19, 2009
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment