На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Г?

Для решения этой задачи нужно посчитать количество путей из города А в город Л, проходящих через город Г. Это значит, что путь состоит из двух частей: от А до Г и от Г до Л. 1. Количество путей из А в Г: Из А в Г ведет 2 дороги (напрямую и через В). - А → Г (1 путь) - А → В → Г (1 путь) Итого из А в Г: 1 + 1 = 2 пути. 2. Количество путей из Г в Л: Посчитаем количество путей в каждый город, начиная от Г: - Г: 1 путь (начальная точка для этого участка) - З: ведет дорога из Г (1) + из В (А->В->З, путь из В тоже посчитаем). Проще по узлам: - Г = 1 - З = Г + В + Д. Посмотрим, сколько путей ведут в Г, В, Д из А: - А = 1 - Б = А = 1 - В = А + Б = 1 + 1 = 2 - Г = А + В = 1 + 2 = 3 - Д = А + Г = 1 + 3 = 4 - З = В + Г + Д = 2 + 3 + 4 = 9 - Е = Б = 1 - И = Е = 1 - Ж = Д + З = 4 + 9 = 13 - Л = И + З + Ж = 1 + 9 + 13 = 23 Теперь рассмотрим условие «проходящих через город Г». Наши пути должны выглядеть так: А → ... → Г → ... → Л. Количество путей из А в Г равно 3 (А→Г, А→В→Г, А→Б→В→Г). Количество путей из Г в Л: - Г = 1 - З = Г (из З ведут дороги из В и Д, но нам нужны пути строго через Г). Считаем только те, что выходят из Г. - Г = 1 - З = Г = 1 (путь Г→З) - Ж = Г + З = 1 + 1 = 2 (пути Г→Ж и Г→З→Ж) - Л = З + Ж = 1 + 2 = 3 (пути Г→З→Л, Г→З→Ж→Л, Г→Ж→Л) Итого: 3 (пути А->Г) * 3 (пути Г->Л) = 9. Ответ: 9