Блог пользователя maverick00

Graph Doubt

Автор maverick00, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

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.
→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Okk . Got it . Thanks a lot .

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится

      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.

      → Ответить