На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л.

Решим задачи на подсчет количества путей из города А в конечный пункт. Для решения будем подписывать количество путей, ведущих в каждый город, двигаясь от А. Число путей в город равно сумме чисел путей во всех городах, из которых есть дорога в данный город. ### Задача 4 Путь из А в Л, проходящий через И. 1. Сначала считаем пути из А в И: - А = 1 - Б = 1 (А -> Б) - В = 1 (А -> В) - Г = 2 (А -> Г + Б -> Г) - И = 1 (Г -> И) - Далее пути в И не идут, значит, количество путей из А в И равно 1. 2. Теперь считаем пути из И в Л: - И = 1 - Д = 1 (И -> Д) - Е = 1 (И -> Е + Д -> Е) - Ж = 1 (Д -> Ж) - Л = Ж + Е + К (стоп, вернемся) Давай посчитаем граф целиком для точности: - N(А) = 1 - N(Б) = 1 (из А) - N(В) = 1 (из А) - N(Г) = N(А)+N(Б) = 1+1 = 2 - N(Д) = N(Г)+N(Ж) = 2+1 = 3 (Ж из Б) - N(Е) = N(Г)+N(Д)+N(И) = 2+3+1 = 6 - N(И) = N(Г) = 2 - N(Ж) = N(Б) = 1 - N(К) = N(В)+N(Г)+N(И)+N(Е) = 1+2+2+6 = 11 - N(Л) = N(Ж)+N(Д)+N(Е)+N(К) = 1+3+6+11 = 21 Путь должен проходить через И. Значит, нам нужны только пути А -> ... -> И -> ... -> Л. Количество путей А -> И = 2 (через Г). Количество путей И -> Л: - N(И)=1 - N(Е) = 1 (из И) - N(К) = N(И)+N(Е) = 1+1 = 2 - N(Л) = N(Е)+N(К) = 1+2 = 3 Итого: 2 * 3 = 6. **Ответ: 6** ### Задача 5 Путь из А в Н. - N(A) = 1 - N(B) = N(A) = 1 - N(C) = N(A) + N(B) + N(D) = 1 + 1 + 1 = 3 - N(D) = N(A) = 1 - N(E) = N(B) + N(C) = 1 + 3 = 4 - N(F) = N(C) + N(D) = 3 + 1 = 4 - N(G) = N(E) = 4 - N(H) = N(E) + N(G) + N(F) = 4 + 4 + 4 = 12 **Ответ: 12**