Задача:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Ж?
(На рисунке изображен граф с направленными ребрами)
Решение:
Для решения этой задачи мы будем использовать метод подсчета путей, двигаясь от начального города А к конечному городу Л, но с обязательным прохождением через город Ж. Это означает, что мы должны найти количество путей из А в Ж, а затем количество путей из Ж в Л, и перемножить эти значения.
Обозначим \(N(X)\) количество путей из города А в город X.
Шаг 1: Находим количество путей из города А в город Ж.
Начнем с города А:
\(N(А) = 1\) (это начальная точка)
Теперь подсчитываем пути до каждого города, в который можно попасть из А, и так далее, пока не дойдем до Ж. Учитываем только те пути, которые ведут к Ж или могут привести к Ж.
- Б: Из А в Б. \(N(Б) = N(А) = 1\).
- В: Из А в В. \(N(В) = N(А) = 1\).
- Г: Из А в Г. \(N(Г) = N(А) = 1\).
- Д: Из А в Д. \(N(Д) = N(А) = 1\).
Теперь города, в которые можно попасть из Б, В, Г, Д:
- Е: Из Б в Е. \(N(Е) = N(Б) = 1\).
- З: Из Б в З, из В в З, из Г в З. \(N(З) = N(Б) + N(В) + N(Г) = 1 + 1 + 1 = 3\).
- Ж: Из Г в Ж, из Д в Ж. \(N(Ж) = N(Г) + N(Д) = 1 + 1 = 2\).
Итак, количество путей из А в Ж равно 2.
Шаг 2: Находим количество путей из города Ж в город Л.
Теперь мы начинаем от города Ж и считаем пути до Л. Обозначим \(N'(X)\) количество путей из города Ж в город X.
\(N'(Ж) = 1\) (это новая начальная точка для этого этапа)
Теперь подсчитываем пути до каждого города, в который можно попасть из Ж, и так далее, пока не дойдем до Л.
- З: Из Ж в З. \(N'(З) = N'(Ж) = 1\).
- К: Из Ж в К. \(N'(К) = N'(Ж) = 1\).
Теперь города, в которые можно попасть из З, К:
- Л: Из З в Л, из К в Л. \(N'(Л) = N'(З) + N'(К) = 1 + 1 = 2\).
Итак, количество путей из Ж в Л равно 2.
Шаг 3: Перемножаем количество путей.
Общее количество путей из А в Л, проходящих через Ж, равно произведению количества путей из А в Ж и количества путей из Ж в Л.
Общее количество путей = \(N(\text{А} \to \text{Ж}) \times N(\text{Ж} \to \text{Л})\)
Общее количество путей = \(2 \times 2 = 4\)
Ответ: 4