ISRO2020-32

Question

$G$ is an undirected graph with vertex set $\{v1, \ v2, \ v3, \ v4, \ v5, \ v6, \ v7\}$ and edge set $\{v1v2,\ v1v3,\ v1v4\ ,v2v4,\ v2v5,\ v3v4,\ v4v5,\ v4v6,\ v5v6,\ v6v7\ \}$. A breadth first search of the graph is performed with $v1$ as the root node. Which of the following is a tree edge?

• A. $v2v4$
• B. $v1v4$
• C. $v4v5$
• D. $v3v4$

Answer 1

Here in the below page, we can see that v1v4, v4v5 both can be a tree edge. It depends on what we are selecting first as a node to traverse if after v1 v4 is selected then v4v5 would also be a tree edge.

Comments

V1V4 edge is the only edge which you will find in any BFS traversal.

Other edges which is given in option will present based on which order you have traversed

---

See here it is asked which will be a tree edge  not that which would be common for all and also one more thing only v4v5 could be the other option .Other two can never be the edge of the tree for root node being 1

---

As you can see even here  v4v5 can be an edge of the tree.

Answer 2

Of all the given options, Option A is only possible.

Comments

This is BFS, not DFS. There is an edge from V1 to V4, hence the tree edge

---

Answer should be B. v1v4

Answer 3

V1 is adjacent to V2,V3,V4 

so queue state will be

V1

V2

V3

V4

V5

After V1 is popped the queue will contain V2 V3 V4 and V5

Note: the above elements can appear in any order after V1

so, V4 can be popped first and you may think that the answer is V4V5. But here V2 V3 and V5 can also be popped first. so V4V5 may be an edge which will not be included in the BFS tree(as V2 also has an edge to V5).

But V1V4 edge will always be included in the BFS tree as we have taken V1 as the root.

So, answer is b)V1V4