What is the number of routes from \(P\) to \(Q\) in the network shown?
Show Hint
Trace every left-to-right arrow path from \(P\) to \(Q\) one node at a time, and count separately the routes through node 1, through node 2 directly, and through node 3, being careful not to double count paths that reach node 2 via node 1 or node 3.
Step 1: Map out every arrow in the network.
Starting at \(P\), three arrows lead out: \(P \to 1\), \(P \to 2\), and \(P \to 3\).
From node 1, arrows lead to node 2, node 4, and node 5.
From node 2, whether reached from \(P\) or from node 1, arrows lead to node 4 and node 5.
From node 3, arrows lead to node 2 and to node 4.
Finally, both node 4 and node 5 have a single arrow into \(Q\).
Step 2: Count the routes that pass through node 1.
From node 1 you can go straight to 4, straight to 5, or detour through 2 first.
That gives four routes: \(P \to 1 \to 4 \to Q\), \(P \to 1 \to 5 \to Q\), \(P \to 1 \to 2 \to 4 \to Q\), \(P \to 1 \to 2 \to 5 \to Q\).
Step 3: Count the routes that pass through node 2 directly from P.
From node 2 you can go to 4 or to 5, giving two more routes: \(P \to 2 \to 4 \to Q\) and \(P \to 2 \to 5 \to Q\).
Step 4: Count the routes that pass through node 3.
From node 3 you can go straight to 4, or detour through 2 first and then reach either 4 or 5.
That gives three routes: \(P \to 3 \to 4 \to Q\), \(P \to 3 \to 2 \to 4 \to Q\), \(P \to 3 \to 2 \to 5 \to Q\).
Final Answer:
Adding every branch: 4 routes through node 1, plus 2 routes through node 2, plus 3 routes through node 3.
\[ 4 + 2 + 3 = 9 \]
\[ \boxed{9} \]
