Решение задачи: Найти количество путей из А в Л, не проходящих через Ж

Задача:

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

(На рисунке изображен граф с направленными ребрами)

Решение:

Для решения этой задачи мы сначала найдем общее количество путей из города А в город Л. Затем найдем количество путей из города А в город Л, которые проходят через город Ж. И, наконец, вычтем второе из первого, чтобы получить количество путей, не проходящих через город Ж.

Обозначим \(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(Г) + N(Ж)\). Пока не можем посчитать, так как \(N(Ж)\) еще не известно.
• Ж: Из Г в Ж, из Д в Ж. \(N(Ж) = N(Г) + N(Д) = 1 + 1 = 2\).

Теперь можем посчитать \(N(З)\):

• З: \(N(З) = N(Б) + N(В) + N(Г) + N(Ж) = 1 + 1 + 1 + 2 = 5\).

Далее:

• И: Из Е в И. \(N(И) = N(Е) = 1\).
• К: Из Ж в К. \(N(К) = N(Ж) = 2\).

Наконец, город Л:

• Л: Из Е в Л, из З в Л, из И в Л, из К в Л. \(N(Л) = N(Е) + N(З) + N(И) + N(К) = 1 + 5 + 1 + 2 = 9\).

Итак, общее количество путей из А в Л равно 9.

Шаг 2: Находим количество путей из города А в город Л, проходящих через город Ж.

Это было решено в предыдущей задаче (Задание 17). Повторим расчет:

Количество путей из А в Ж:

• \(N(А) = 1\)
• \(N(Г) = N(А) = 1\)
• \(N(Д) = N(А) = 1\)
• \(N(\text{Ж}) = N(Г) + N(Д) = 1 + 1 = 2\)

Количество путей из Ж в Л:

• \(N'(\text{Ж}) = 1\) (начало от Ж)
• \(N'(\text{З}) = N'(\text{Ж}) = 1\)
• \(N'(\text{К}) = N'(\text{Ж}) = 1\)
• \(N'(\text{Л}) = N'(\text{З}) + N'(\text{К}) = 1 + 1 = 2\)

Количество путей из А в Л, проходящих через Ж = \(N(\text{А} \to \text{Ж}) \times N(\text{Ж} \to \text{Л}) = 2 \times 2 = 4\).

Шаг 3: Находим количество путей, не проходящих через город Ж.

Для этого вычтем количество путей, проходящих через Ж, из общего количества путей:

Пути (не через Ж) = Общее количество путей - Пути (через Ж)

Пути (не через Ж) = \(9 - 4 = 5\)

Ответ: 5