Решение задачи: Найти количество путей из А в К (без Г)

Для решения этой задачи воспользуемся методом динамического программирования, последовательно подсчитывая количество путей в каждый город. По условию, нам нужно найти количество путей из города А в город К, которые не проходят через город Г. Это означает, что мы можем просто исключить город Г и все дороги, ведущие в него или из него, из наших расчетов. Обозначим \( N(X) \) — количество путей из города А в город X. 1. Начальная точка: \[ N(A) = 1 \] 2. Город Б: В город Б ведет только одна дорога из А. \[ N(B) = N(A) = 1 \] 3. Город Г: По условию пути не должны проходить через Г, поэтому: \[ N(G) = 0 \] 4. Город В: В город В ведут дороги из А и Б. Дорога из Г не учитывается. \[ N(V) = N(A) + N(B) = 1 + 1 = 2 \] 5. Город Е: В город Е ведут дороги из Б и В. \[ N(E) = N(B) + N(V) = 1 + 2 = 3 \] 6. Город Ж: В город Ж ведут дороги из В и Е. Дорога из Г не учитывается. \[ N(Zh) = N(V) + N(E) = 2 + 3 = 5 \] 7. Город Д: В город Д ведут дороги из В и Е. \[ N(D) = N(V) + N(E) = 2 + 3 = 5 \] 8. Город К: В город К ведут дороги из Е, Д и Ж. \[ N(K) = N(E) + N(D) + N(Zh) = 3 + 5 + 5 = 13 \] Ответ: 13.