CameraIcon
CameraIcon
SearchIcon
MyQuestionIcon
MyQuestionIcon
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 1 to vertex 100 is

A
99
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
23
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
7
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
D
4
No worries! We‘ve got your back. Try BYJU‘S free classes today!
Open in App
Solution

The correct option is C 7
In graph G there is a directed edge between i to j where j is either i + 1 or 3i


Since minimum values is finding, so we need to make edge which have maximum difference in i and j here (99 - 33) = 66 is maximum.

So 7 edges are needed.

flag
Suggest Corrections
thumbs-up
0
similar_icon
Similar questions
View More
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Quadrilaterals and their Properties
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon