Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding all cycles in an undirected graph

If I have an undirected graph, how can I get a list of all cycles?

For example, from the following graph, I would want the cycles:

(a,b,d,e,c)
(a,b,c)
(b,d,e)

enter image description here

like image 235
YXD Avatar asked Feb 21 '11 15:02

YXD


2 Answers

this is not possible in polynomial time as if possible then we could use this to find all cycles and hence cycle of largest length which implies we can solve hamiltonian cycle problem completely in polynomial time.

like image 144
Akk Avatar answered Nov 07 '22 12:11

Akk


You presumably want only simple cycles (those that don't repeat a vertex), or there's an infinite number of them. Even then, there can be an exponential number of cycles. Perhaps this isn't the problem you really want to solve?

like image 1
Keith Randall Avatar answered Nov 07 '22 11:11

Keith Randall