search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
2 votes
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.

in Graph Theory
retagged by
550 views

2 Answers

4 votes
 
Best answer
  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$)$

Reference: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm


selected by
0 votes
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

4 votes
1 answer
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.
asked Nov 27, 2016 in Probability makhdoom ghaya 559 views
32 votes
3 answers
2
8.5k views
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$
asked Jun 1, 2015 in DS Anu 8.5k views
1 vote
0 answers
3
273 views
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.
asked Jun 2, 2016 in Graph Theory jothee 273 views
21 votes
2 answers
4
1.8k views
Which of the following graphs is/are planner?
asked Nov 27, 2016 in Graph Theory makhdoom ghaya 1.8k views
...