GATE1989-4-vii

550 views

Provide short answers to the following questions:

In the graph shown above, the depth-first spanning tree edges are marked with a 'T'. Identify the forward, backward and cross edges.

retagged

1. tree edge (T) is an edge in a DFS-tree.
2. back edge (B) connects a vertex to an ancestor in a DFS-tree. (Includes a self-loop and this indicates the presence of a cycle)
3. forward edge (F) is a non-tree edge that connects a vertex to a descendent in a DFS-tree.
4. cross edge (C) is any other edge in graph $G.$ It either connects vertices in two different DFS tree or two vertices in the same DFS tree neither of which is the ancestor of the other.

For the given question,

• Forward Edges: $1 \to 3, 2 \to 4$
• Back Edges: $4 \to 5$
• Cross Edges: $3 \to 7, 4 \to 6, 3\to 8, 4\to 8$

These are marked in the below graph. Below each node, its discovery time is marked. An edge $(u,v)$ becomes a forward edge only if $d(u) < d(v).$

PS:

• An edge $(u, v)$ is a cross edge if and only if $d[v] < f[v] < d[u] < f[u].$ $(v$ is discovered and finished before $u$ is discovered$)$
• An edge $(u, v)$ is a back edge if and only if $d[v] < d[u] < f[u] < f[v].$ $(v$ is discovered first and before it finishes $u$ is discovered and finished$)$

selected
FE- (2,4),(1,3),(3,8),(4,8)

BE-(4,5)

CE-(3,7),(4,6)
1
(3,8), (4,8) are cross edges as their discovery and finishing times are of form {d[u],f[u]} {d[v],f[v]}

Related questions

1
559 views
Answer the following: Which of the following statements are FALSE? For poisson distribution, the mean is twice the variance. In queuing theory, if arrivals occur according to poisson distribution, then the inter-arrival time is exponentially distributed. The ... the time between successive arrivals is exponential, then the time between the occurences of every third arrival is also exponential.
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols $S1$ to $S7$ initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is $4$ $5$ $6$ $3$
A fan of order $n$ is a graph on the vertices $\{0, 1, \dots, n\}$ with $2n − 1$ edges defined as follows: vertex $0$ is connected by an edge to each of the other $n$ vertices, and vertex $i$ is connected by an edge to vertex $i + 1$, ... $n$. Calculate $f_4$. Write a recurrence for $f_n$. Solve for fn using ordinary generating functions.