Discussion
Let \(G(V, E)\) be an undirected and unweighted graph with 100 vertices. Let \(d(u, v)\) denote the number of edges in a shortest path between vertices \(u\) and \(v\) in \(V\). Let the maximum value of \(d(u, v)\), \(u, v \in V\) such that \(u \ne v\), be 30. Let \(T\) be any breadth-first-search tree of \(G\). Which ONE of the given options is CORRECT for every such graph \(G\)?
Answer: C
The correct statement is The height of \(T\) is at least 15.
A BFS tree rooted at r has height equal to the largest distance from r to any vertex, the eccentricity of r. Take u, v at the maximum distance 30. Both are within distance h of the root, so
\[ \begin{aligned} 30 = d(u, v) &\le d(u, r) + d(r, v) \\ &\le 2h \Rightarrow h \ge 15 \end{aligned} \]
The height depends on where the BFS starts. In a graph shaped like a path of 31 vertices (with the other vertices attached near the middle), a BFS from the middle has height 15, while a BFS from an end has height 30. So 'exactly 15' and 'exactly 30' are not true for every tree, and 'at least 30' fails for the tree rooted in the middle.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development