Question:
The figure below shows the network connecting cities A, B, C, D, E and F. The arrows indicate permissible direction of travel. What is the number of distinct paths from A to F?
The figure below shows the network connecting cities A, B, C, D, E and F. The arrows indicate permissible direction of travel. What is the number of distinct paths from A to F?
Show Hint
Read the arrows from the figure and count the paths backwards from F: the number of paths from a city is the sum of the numbers of paths from the cities it points to.
Updated On: Nov 4, 2026
- 9
- 11
- 10
- None of these
Show Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
Step 1: Read the arrows in the figure:
A \(\to\) B, A \(\to\) D; B \(\to\) C, B \(\to\) D, B \(\to\) E, B \(\to\) F; C \(\to\) E, C \(\to\) F; D \(\to\) C, D \(\to\) E; E \(\to\) F.
Step 2: Count paths to F, working backwards:
From E: 1 path (E-F).
From C: C-F and C-E-F, so 2 paths.
From D: D-C (2 paths) + D-E (1 path) = 3 paths.
From B: B-C (3) + B-D (2) + B-E (1) + B-F (1) = 7 paths.
From A: A-B (7) + A-D (2) = 10 paths.
Step 3: List them to confirm:
Through B: ABF, ABCF, ABCEF, ABEF, ABDEF, ABDCF, ABDCEF (7).
Through D: ADEF, ADCF, ADCEF (2).
Total: 10.
Final Answer:
The correct option is (3): 10.
A \(\to\) B, A \(\to\) D; B \(\to\) C, B \(\to\) D, B \(\to\) E, B \(\to\) F; C \(\to\) E, C \(\to\) F; D \(\to\) C, D \(\to\) E; E \(\to\) F.
Step 2: Count paths to F, working backwards:
From E: 1 path (E-F).
From C: C-F and C-E-F, so 2 paths.
From D: D-C (2 paths) + D-E (1 path) = 3 paths.
From B: B-C (3) + B-D (2) + B-E (1) + B-F (1) = 7 paths.
From A: A-B (7) + A-D (2) = 10 paths.
Step 3: List them to confirm:
Through B: ABF, ABCF, ABCEF, ABEF, ABDEF, ABDCF, ABDCEF (7).
Through D: ADEF, ADCF, ADCEF (2).
Total: 10.
Final Answer:
The correct option is (3): 10.
Was this answer helpful?
0
0
Top CAT Quantitative Aptitude Questions
- In a triangle ABC,AB=AC=8cm. A circle drawn with BC as diameter passes through A. Another circle drawn with center at A passes through B and C. Then the area,in sq.cm,of the overlapping region between the two circles is
- The simple interest accrued on an amount of Rs.25,000 at the end of three years is Rs.7,500. What would be the compound interest accrued on the same amount at the same rate in the same period?
- What is the sum of all roots of the equation \(|x+4|^2–10|x+4|=24\)?
- A solid metal sphere is melted and smaller spheres of equal radii are formed. 10% of the volume of the sphere is lost in the process. The smaller spheres have a radius which is \(\frac{1}{9}\text{th}\) the larger sphere. If 10 litres of paint were needed to paint the larger sphere,how many litres are needed to paint all the smaller spheres?
- The ratio of the ages of a husband and his wife when they got married was 6:5. 4 years and 6 years after their marriage they had their 1st and 2nd children. The sum of the present ages of the husband and wife is 6.4 times the sum of the present ages of their children. The average age of the family at present is 18.5 years. Find the ratio of the ages of the husband and wife when their second child was born.
View More Questions
Top CAT Graph Theory Questions
- Three Englishmen and three Frenchmen work for the same company. Each of them knows a secret not known to others. They need to exchange these secrets over person-to-person phone calls so that eventually each person knows all six secrets. None of the Frenchmen knows English, and only one Englishman knows French. What is the minimum number of phone calls needed for the above purpose?
- In a six-node network, two nodes are connected to all the other nodes. Of the remaining four, each is connected to four nodes. What is the total number of links in the network?
- Four cities are connected by a road network as shown in the figure (a triangle with vertices and a centroid-like point connected to all three vertices). In how many ways can you start from any city and come back to it without travelling on the same road more than once?
- ABCDEFGH is a regular octagon. A and E are opposite vertices of the octagon. A frog starts jumping from vertex to vertex, beginning from A. From any vertex of the octagon except E, it may jump to either of the two adjacent vertices. When it reaches E, the frog stops and stays there. Let \( a_n \) be the number of distinct paths of exactly \( n \) jumps ending in E. Then, what is the value of \( a_{2n-1} \)?
DIRECTIONS for the following questions: These questions are based on the situation given below: In each of the questions a pair of graphs F(x) and F1(x) is given. These are composed of straight-line segments, shown as solid lines, in the domain \( x \in (-2, 2) \).
choose the answer as
a. If F1(x) = - F(x)
b. if F1(x) = F(- x)
c. if F1(x) = - F(- x)
d. if none of the above is trueQuestion 89
Question 90
Question 91
Question 92
Top CAT Questions
- Compare and contrast between Portia and Jessica characters in Merchant of Venice.
- In a triangle ABC,AB=AC=8cm. A circle drawn with BC as diameter passes through A. Another circle drawn with center at A passes through B and C. Then the area,in sq.cm,of the overlapping region between the two circles is
- The simple interest accrued on an amount of Rs.25,000 at the end of three years is Rs.7,500. What would be the compound interest accrued on the same amount at the same rate in the same period?
- What is the sum of all roots of the equation \(|x+4|^2–10|x+4|=24\)?
- A solid metal sphere is melted and smaller spheres of equal radii are formed. 10% of the volume of the sphere is lost in the process. The smaller spheres have a radius which is \(\frac{1}{9}\text{th}\) the larger sphere. If 10 litres of paint were needed to paint the larger sphere,how many litres are needed to paint all the smaller spheres?
View More Questions