| 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.