Register

ISRO2020-32

• edited by
4,063 views
2 votes
2 votes

$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?

  1. $v2v4$
  2. $v1v4$
  3. $v4v5$
  4. $v3v4$
• edited by
User Avatar

3 Answers

1 votes
1 votes

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.


User Avatar
0 votes
0 votes

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

User Avatar
0 votes
0 votes

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

 

 

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

6 votes
6 votes
3 answers
1
Satbir asked Jan 13, 2020
3,331 views
ISRO2020-71
Of the following, which best approximates the ratio of the number of nonterminal nodes in the total number of nodes in a complete $K$-ary tree of depth $N$ ? $1/N$ $N-1/N$ $1/K$ $K-1/K$
Of the following, which best approximates the ratio of the number of nonterminal nodes in the total number of nodes in a complete $K$-ary tree of depth $N$ ?$1/N$$N-1/N$$...
User Avatar
4 votes
4 votes
3 answers
2
Satbir asked Jan 13, 2020
2,953 views
ISRO2020-4
Convert the pre-fix expression to in-fix $- ^{\ast} +ABC^{\ast} – DE+FG$ $(A-B)^{\ast}C+(D^{\ast}E)-(F+G)$ $(A+B)^{\ast}C-(D-E)^{\ast}(F+G)$ $(A+B-C)^{\ast}(D-E)^{\ast}(F+G)$ $(A+B)^{\ast}C-(D^{\ast}E)-(F+G)$
Convert the pre-fix expression to in-fix $- ^{\ast} +ABC^{\ast} – DE+FG$$(A-B)^{\ast}C+(D^{\ast}E)-(F+G)$$(A+B)^{\ast}C-(D-E)^{\ast}(F+G)$$(A+B-C)^{\ast}(D-E)^{\ast}(F+...
User Avatar
5 votes
5 votes
3 answers
3
Satbir asked Jan 13, 2020
5,832 views
ISRO2020-20
The minimum height of an AVL tree with $n$ nodes is $\text{Ceil } (\log_2(n+1))$ $1.44\ \log_2n$ $\text{Floor } (\log_2(n+1))$ $1.64\ \log_2n$
The minimum height of an AVL tree with $n$ nodes is$\text{Ceil } (\log_2(n+1))$$1.44\ \log_2n$$\text{Floor } (\log_2(n+1))$$1.64\ \log_2n$
User Avatar
Link Copied!