Graph - Discrete Structures

Question 1 UGC NET June-2020
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 if and only if either j=i+1 or j=3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is _.

A – 23

B – 99

C – 4

D – 7

Show Answer With Best Explanation

Answer: D
Explanation :
Edge set consists of edge from i to j , if and only if
either j=i+1
or j=3i
since, we to find the minimum number of edge from vertex 1 to vertex 100.so, we have to think about how we can reach an edge 100 from an edge 1 with minimum path.
1 ->3 ->9 -> 10 -> 11 -> 33 -> 99 -> 100.
We need minimum 7 edges.