edited by
10,453 views
57 votes
57 votes

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

  1. $4$
  2. $7$
  3. $23$
  4. $99$
edited by

3 Answers

Best answer
88 votes
88 votes

Edge set consists of edges from $i$ to $j$ using either 

  1. $ j = i+1$ (or)
  2. $ j=3i.$

Second option will help us reach from $1$ to $100$ rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from $1$ to $100$, try to find a path from $100$ to $1$.

The edge sequence with minimum number of edges is $1\rightarrow3\rightarrow9\rightarrow10\rightarrow11\rightarrow33\rightarrow99 - 100$ which consists of $7$ edges. 
The answer is option ($B$).

edited by
65 votes
65 votes

The conditions are given
Edge set consists of edges from i to j using either

  1.  j = i+1 OR
  2.  j=3i

What we think from here :  Minimum we take vertex 1 max we take vertex 100


Now one important point is to reach 100 the maximum number  which gets   j = 3*i where i= 33 so j = 3*33 = 99


Half problem is solved.
We got                                                                   1--33--99--100
Now see to reach 33 how many minimum edges needed.
Maximum number between which get value j= 3i, i= 11 so j= 3*11= 33


What we get                                                               1--11--33--99--100
So, problem solved almost minimum edge need to reach 11 from 1


Max number i which get j= 3i, i= 3 so j= 3*i =9 to reach 11 ..9--10--11
So we got another point
                                                                                  1--9--10--11--33--99--100

Now to reach 11 from 1
Max value of i = 3 so j= 3*i= 9 so 3--9
                                                                                 1--3--9--10--11--33--99--100

Note: Solved problem into half give u an idea how to get minimum for rest of the graph.

edited by
0 votes
0 votes
The desired path (from end to begin) will be 100--99--33--11--10--9--3—1

The edges between them is as per the condition mentioned in the question. Hence min. path length is 7.
Answer:

Related questions

38 votes
38 votes
4 answers
1
gatecse asked Sep 21, 2014
11,534 views
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is:$1...
34 votes
34 votes
2 answers
2
Ishrat Jahan asked Nov 2, 2014
12,922 views
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$?$10$$11$...
25 votes
25 votes
8 answers
3
Ishrat Jahan asked Nov 1, 2014
6,914 views
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices?$n-1$$n$$n+1$$2n-1$
37 votes
37 votes
7 answers
4
Ishrat Jahan asked Oct 31, 2014
8,718 views
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is aHamiltonian cyclegri...