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

Question

Вопрос:

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

Фотография

Ответ ассистента

Accepted Answer

Для решения задачи воспользуемся методом подсчета количества путей в ориентированном графе. Будем последовательно находить количество путей от города A до каждого следующего города: 1. $N(A) = 1$ (начальная точка). 2. $N(B) = N(A) = 1$. 3. $N(C) = N(A) + N(B) + N(D) = 1 + 1 + 1 = 3$. 4. $N(D) = N(A) = 1$. 5. $N(E) = N(B) + N(C) = 1 + 3 = 4$. 6. $N(F) = N(C) = 3$. 7. $N(G) = N(C) + N(E) + N(F) = 3 + 4 + 3 = 10$. 8. $N(H) = N(E) + N(G) = 4 + 10 = 14$. **Ответ: 14**

Ответ ассистента

Другие решения