Question:
The network diagram shows cities A, B, C, D, E, F with arrows as permissible travel. How many distinct paths exist from A to F?
The network diagram shows cities A, B, C, D, E, F with arrows as permissible travel. How many distinct paths exist from A to F?
Show Hint
For path counting in DAGs, work backwards from destination, summing incoming edges’ path counts.
Updated On: Aug 4, 2025
- 9
- 10
- 11
- None of these
Hide Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
List paths manually or use dynamic counting:
From E to F = 1 path, C to F = 1, D to F = 1.
E gets from B: add B$\to$E direct plus via C etc. Count stepwise gives total 11.
From E to F = 1 path, C to F = 1, D to F = 1.
E gets from B: add B$\to$E direct plus via C etc. Count stepwise gives total 11.
Was this answer helpful?
0
0
Top Questions on Graph Theory
- A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, \( n \) is _______.
- Dijkstra's algorithm fails for graphs with _______.
- Assume G is a simple undirected graph and some vertices of G are of odd degree. Add a node \( v \) to G and make it adjacent to each odd degree vertex of G, then the resultant graph is sure to be _______.
- A subgraph H of a graph G is called a clique if _______.
- For a given graph G having \( v \) vertices and \( e \) edges which is connected and has no cycles, which of the following statements is true?
View More Questions
Questions Asked in CAT exam
- ABCD is a rectangle with sides AB = 56 cm and BC = 45 cm, and E is the midpoint of side CD. Then, the length, in cm, of radius of incircle of \(\triangle ADE\) is
- CAT - 2024
- Mensuration
- Two places A and B are 45 kms apart and connected by a straight road. Anil goes from A to B while Sunil goes from B to A. Starting at the same time, they cross each other in exactly 1 hour 30 minutes. If Anil reaches B exactly 1 hour 15 minutes after Sunil reaches A, the speed of Anil, in km per hour, is
- CAT - 2024
- Time, Speed and Distance
- The selling price of a product is fixed to ensure 40% profit. If the product had cost 40% less and had been sold for 5 rupees less, then the resulting profit would have been 50%. The original selling price, in rupees, of the product is
- CAT - 2024
- Profit and Loss
- Suppose $x_1, x_2, x_3, \dots, x_{100}$ are in arithmetic progression such that $x_5 = -4$ and $2x_6 + 2x_9 = x_{11} + x_{13}$. Then, $x_{100}$ equals ?
- CAT - 2024
- Arithmetic Progression
- A circular plot of land is divided into two regions by a chord of length $10\sqrt{3}$ meters such that the chord subtends an angle of $120^\circ$ at the center. Then, the area, in square meters, of the smaller region is
- CAT - 2024
- Mensuration
View More Questions