Graph Algorithm 3

16Let 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 1 to vertex 100 is

Option : B
Explanation :
Edge set consist edges it j = i + 1 or j = 3i
The edge sequence with minimum no of edges is
1 – 3 – 9 – 10 – 11
|
100 – 99 – 33
Which consist 7 edges

Forgot your password?

I agree with the Terms.