What kind of edge do we have?

144 Views Asked by At

In order to find the kind of the edges of a graph, at which we applied the Depth-first search algorithm, we could use this:

$$\begin{bmatrix} \text{ tree edges: } x \to y & [d[y],f[y]] \subset [d[x],f[x]] \\ \\ \text{forward edges: } x \to y & [d[x],f[x]] \subset [d[y],f[y]] \\ \\ \text{back edges: } x \to y & [d[y],f[y]] \subset [d[x],f[x]] \\ \\ \text{Cross edges: } x \to y & [d[x],f[x]] \cap [d[y],f[y]]=\varnothing \end{bmatrix}$$

But, when we have for example the case $[d[y],f[y]] \subset [d[x],f[x]]$ how can we know if it is a tree edge or a back edge?

EDIT:

Discovery Time: The discovery time $d[v]$ is the number of nodes discovered or finished before first seeing $v$.

Finishing Time: The finishing time $f[v]$ is the number of nodes discovered or finished before finishing the expansion of $v$.

That's the graph I am looking at:

enter image description here

And here are the discovery and finish times I found:

enter image description here

EDIT: Algorithm:

Depthfirstsearch(G)
   for each v ∈ V
        color[v]=white
        p[v]=NIL
   time=0
   for each v ∈ V
       if color[v]=white then
          Visit(v)


Visit(u)
  color[u]=gray
  time=time+1
  d[u]=time
  for each v ∈ Adj[u]
       if color[v]=white then
          p[v]=u
          Visit(v)
  color[u]=black
  time=time+1
  f[u]=time

EDIT:

At the beginning the colours that the nodes get, are the following:

enter image description here

At which step do we look at the colors that the nodes got in order to check the type of the edges?

EDIT:

enter image description here

1

There are 1 best solutions below

10
On BEST ANSWER

An edge $x \to y$ is a tree edge iff $y$ was first discovered when DFS traversed the edge $x \to y$. If we only have access to the discovery and finishing times (and we can't just modify the DFS algorithm), then an equivalent condition is that $x \to y$ is a tree edge iff for any other vertex $z \neq y$, we have that: $$ [d[z], f[z]] \subset [d[x], f[x]] \implies [d[z], f[z]] \subset [d[y], f[y]] \subset [d[x], f[x]] $$ In other words, $[d[y], f[y]]$ is the largest possible proper subset of $[d[x], f[x]]$.