How can we detect a simple cycle in a graph ?
Simple Cycle : "Let us denote as a simple cycle a set of v vertices that can be numbered so that the edges will only exist between vertices number 1 and 2, 2 and 3, ..., v - 1 and v, v and 1. "
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
How can we detect a simple cycle in a graph ?
Simple Cycle : "Let us denote as a simple cycle a set of v vertices that can be numbered so that the edges will only exist between vertices number 1 and 2, 2 and 3, ..., v - 1 and v, v and 1. "
Name |
---|
How to "detect" a simple cycle is actually quite easier than how to "find" one.
Consider any connected component of a graph. Let the size of the connected component be N and the number of edges in it be M. The inequality $$$N-1 \le M$$$ must hold, because a graph with N-1 edges is a tree, and removing any edge from a tree causes it to be disconnected.
I claim that any connected component that satisfies $$$M \ge N$$$ has a loop. Proof: Consider the spanning tree of said connected component. This spanning tree only uses up $$$N-1$$$ of the M edges. Since adding any edge to a tree creates a loop, there is at least one loop in this connected component.
Okk . Got it . Thanks a lot .
To implement that, it is usually easiest to use a disjoint set and just check if the two positions were already connected. If there were, you have a cycle.