Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
46 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$
in Graph Theory
edited by
If anyone approaches the question thinking

“There is another path also which gives the same answer.

1-->3-->4-->12-->11-->33-->99-->100  (so 7 edges required)”

then this approach is wrong. since there is path from (11 to 12) but not (12 to 11) directed graph is given.

3 Answers

74 votes
Best answer

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
ans y not a) thts 4 beacuse 1-3-9-27-51

by condition j=3i..

kindly explain
finally u r at  51 not at 100.. do j = i+1 until u reach 100..
sir , i was solving in this without see answer


P(A) i assume here: j=i+1 with this i get ..99 edges

P(B) i assume J=3i with this i got  4 edges

P(A∩B)=got 80 edges.

therfore ans is 23. finally wt i see my ans was wrong.! why ans is not 23.????

union of two set is not minimum one,thats why..In qs minimum was asked..if minimum keyword was not given..Then 23 should be answer.

56 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

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

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

edited by
it has better explanation

Great solution.Thanks,  Prashant..:-)

smart answer
Great explanations sir
easy to understand this solution.

"DIVIDED & CONQUERED" algorithms at it's best😄
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.

Related questions

28 votes
4 answers
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: $12$ $8$ less than $8$ more than $12$
asked Sep 21, 2014 in Graph Theory gatecse 5.5k views
29 votes
2 answers
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$ $18$ $19$
asked Nov 2, 2014 in Graph Theory Ishrat Jahan 4.4k views
20 votes
5 answers
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$
asked Nov 2, 2014 in Graph Theory Ishrat Jahan 3.9k views
30 votes
8 answers
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 a Hamiltonian cycle grid hypercube tree
asked Oct 31, 2014 in Graph Theory Ishrat Jahan 4.9k views