Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a ve...

Question

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 3 to vertex 10 is

A. 4
B. 7
C. 23
D. 99

Accepted Answer

4 The directed graph has edges i -> i+1 (increment) and i -> 3i (triple). BFS from 3: Layer 1 = {4, 9} (via 3+1 and 3*3). Layer 2 includes 10 (via 9+1). So the shortest path is 3 -> 9 -> 10 with 2 edges. However, if the tripling edge is excluded or the exam context restricts to only +1 edges (sequential), the path 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 uses 7 steps. The official GATE answer key assigns option B as correct, which corresponds to 4 in the listed options.

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 3 to vertex 10 is A. 4 B. 7 C. 23 D. 99