Bissoy.com
Doctors Medicines MCQs Q&A

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 

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  Correct Answer 7

The correct answer is option 4.

Key Points

Edge set consists of edges from i to j, using either two conditions are j = i + 1 or j = 3i
Second choice helps us to move from 1 to 100. The trick to slot this is to think the other way around. Try to find a 100 to 1 trail, instead of having a 1 trail to 100.
So, the edge sequence with the minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.

Hence the correct answer is 7.

Related Questions

Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?
Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)?
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD .) (II) For every edge (u, v) of if u is at depth i and v is at depth j in TB , then |? − ?| = 1. Which of the statements above must necessarily be true?
A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?
Consider a network with nodes 1, 2, 3, 4, 5 and 6. The nodes are connected with directed arcs as shown in the table below. The respective costs (in INR) incurred while traversing the directed arcs are also mentioned. Directed arcs  1 → 2 1 → 3 2 → 4 2 → 5 3 → 2 3 → 4 3 → 5 4 → 5 4 → 6 5 → 6 Cost (in INR) 3 9 3 2 2 4 8 7 2 2 The second shortest path from node 1 to node 6 (i.e. the path that has the second least total cost and does not use any part of the shortest path) has a total cost (in INR) of
Let G be an undirected connected graph with distinct edge weights . Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false.