Question

Consider a directed graph \( G = (V,E) \), where \( V = \{0,1,2,\dots,100\} \) and \[ E = \{(i,j) : 0<j - i \leq 2, \text{ for all } i,j \in V \}. \] Suppose the adjacency list of each vertex is in \textit{decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after vertex 50 is:}

Hint:

When DFS is performed with an adjacency list sorted in decreasing order, higher-numbered vertices are visited first, affecting the traversal order significantly.

Answer 1

Correct Answer: 75

Step 1: Understanding the graph structure.
Each vertex \( i \) has directed edges to \( i+1 \) and \( i+2 \), if they exist.
The adjacency list is sorted in decreasing order, meaning DFS explores the highest-numbered neighbor first. Step 2: DFS traversal starting from vertex 0.
DFS starts at 0 and always visits the highest-numbered connected vertex first.
This results in the traversal order: 0, 2, 4, ..., reaching 100 first.
After backtracking, vertices in the range \( 1, 3, 5, \dots \) get visited.
Step 3: Counting vertices discovered after vertex 50.
Since DFS reaches 100 before backtracking, all vertices from 51 to 100 are discovered after 50.
The number of such vertices is \( 100 - 25 = 75 \).
Thus, the number of vertices discovered after vertex 50 is: \[ 75. \]