Решение задачи: Пути из А в К без города Г

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