1
$\begingroup$

Trying to understand complexity well, I found myself with the following problem.

Consider the following algorithm to detect if an undirected graph $G = (V, E)$ has a cycle.

Imagine that $V = \{1 ...|V|\}$ (in other words that the vertices are numbered from $1$ to $|V|$ ). An explorer plants a flag on point $1$ and then moves on the graph according to the following principle.

  • For each vertex $u \in V$ the different edges $(u,v)$ around the point $u$ can be ordered according to the size of $v$. So we can talk about the ith edge around $u$. . Note that if $(u,v)$ is the ith edge around $u$ it is possible that $(v,u)$ is not the ith edge around from $v$.
  • If the explorer reaches the point $u$ of degree $k$ using the ith edge around $u$ then it starts from $u$ using the $(i + 1)$ th edge around from $u$. If $i = k$ then the explorer starts from the first edge around $u$.

As a first attempt, the explorer leaves point $1$ using the first edge around $1$. If it returns to point $1$ by a different edge then he concludes that $G$ contains a cycle.

If on the other hand it returns to point $1$ to across the same edge, then it begins its exploration again, starting by the second edge of point $1$, then the third edge and so on.

If he has exhausted all edges around $1$ and has always returned to $1$ by the same edge, so he plants his flag on point $2$ and so on.

My questions are :

  1. how can we show that $G$ contains a cycle if and only if there is a point $u$ and an edge $(u,v)$ around $u$ such that the explorer leaving $u$ by the edge $(u,v)$ does not return to $u$ by $(u,v)$.
  2. What is the is the space complexity of the algorithm described here?
$\endgroup$
  • $\begingroup$ thank you for your comment, i try to follow their method but i am a little lost. But I have the impression that it is not quite the same algorithm. $\endgroup$ – tala Apr 10 at 1:07

Browse other questions tagged or ask your own question.