Algorithms Test - 4

352 Views
86 Downloads
PDF 5,210,304 Bytes

GATE
CSE

Algorithms

Test-04Solutions

ALGORITHMS
1. Let G be an undirected graph. Consider a depth-first traversal of G,

and let T be the resulting depth-first search tree. Let u be a vertex
in G and let v be the first new (unvisited) vertex visited after
visiting u in the traversal. Which of the following statements is
always true?
a) {u, v} must be an edge in G, and u is a descendant of v in T
b) {u, v} must be an edge in G, and v is a descendant of z in T
c) If {u, v} is not an edge in G then u is a leaf in T
d) If {u, v} is not an edge in G then u and v must have the same

parent in T
Answer: (c)
Solution:
(c) is always true but (b) & (d) are true in only few cases. (a) is
never true.
2. Difference between flow-chart and target="_blank" href="/jfej/ngpe"> Click to View FlipBook Version Previous Book แบบฝึกทักษะการแก้โจทย์ปัญหาการประยุกต์ของสมการเชิงเส้นตัวแปรเดียว เล่ม 6 Next Book Best age for hair transplant

Data Loading...

Algorithms Test - 4 - PDF Flipbook