retagged by
2,173 views
5 votes
5 votes

Which of the following statements are false ?

$1.$ A depth-first search of a directed graph always produces the same number of tree edges (i.e., independent of the order in which the vertices are provided and independent of the order of the adjacency list).

$2.$ Both DFS and BFS require $\Omega(n)$ storage for their operation.

$3.$ If we double the weight of every edge in the graph shortest path between any two vertices will not change.

$4.$ Dijkstra's algorithm may not terminate if the graph contains negative weight edges.

retagged by

1 Answer

0 votes
0 votes
When we traverse a graph, and we get a tree.

By depth first traversal, we get DFT. So the edges of graph that are present in DFT are called tree edges. There are back edges, cross edges, which are not present in the tree.

So, he is saying in first statement that, no matter how we traverse the graph, we will get the  same number of tree edges.

Which is correct.
edited by

Related questions

0 votes
0 votes
0 answers
2
Akash Kanase asked Jan 15, 2016
386 views
I got that Statement 3 can be false in case we have function 1/n, then its square become 1/n^2. But I don't think statement 2 is true either. Please prove whether I'm cor...
0 votes
0 votes
1 answer
4