maverick00's blog

Graph Doubt

By maverick00, history, 4 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okk . Got it . Thanks a lot .

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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.

      → Reply