На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G и H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Н?

Для решения задачи воспользуемся методом подсчёта количества путей в каждую вершину. **Способ 1: Метод динамического программирования (подсчёт по вершинам)** Будем последовательно вычислять количество способов добраться в каждый город, складывая количество путей из всех городов, из которых в него ведут стрелки. 1. В город $A$ ведёт 1 путь (начало): $A = 1$. 2. Город $C$: ведёт только стрелка из $A$. $C = A = 1$. 3. Город $F$: ведёт только стрелка из $A$. $F = A = 1$. 4. Город $B$: ведут стрелки из $A$ и $C$. $B = A + C = 1 + 1 = 2$. 5. Город $D$: ведут стрелки из $C$ и $B$. $D = C + B = 1 + 2 = 3$. 6. Город $E$: ведут стрелки из $F, B$ и $D$. $E = F + B + D = 1 + 2 + 3 = 6$. 7. Город $G$: ведёт только стрелка из $F$. $G = F = 1$. 8. Город $H$ (финиш): ведут стрелки из $G, E$ и $D$. $H = G + E + D = 1 + 6 + 3 = 10$. **Способ 2: Метод перебора (дерево путей)** Выпишем все возможные маршруты, начиная с города $A$: 1. $A \rightarrow F \rightarrow G \rightarrow H$ 2. $A \rightarrow F \rightarrow E \rightarrow H$ 3. $A \rightarrow B \rightarrow E \rightarrow H$ 4. $A \rightarrow B \rightarrow D \rightarrow E \rightarrow H$ 5. $A \rightarrow B \rightarrow D \rightarrow H$ 6. $A \rightarrow C \rightarrow B \rightarrow E \rightarrow H$ 7. $A \rightarrow C \rightarrow B \rightarrow D \rightarrow E \rightarrow H$ 8. $A \rightarrow C \rightarrow B \rightarrow D \rightarrow H$ 9. $A \rightarrow C \rightarrow D \rightarrow E \rightarrow H$ 10. $A \rightarrow C \rightarrow D \rightarrow H$ **Ответ: 10**