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

Решение:

Эта задача решается методом перебора путей, учитывая направления стрелок. Мы будем считать количество путей, ведущих к каждой вершине.

Обозначим количество путей из А в вершину X как N(X).

1. Начальная точка:

• N(А) = 1 (начинаем с 1 пути)

2. Следующие вершины:

• Б: Из А можно попасть только в Б. N(Б) = N(А) = 1.
• И: Из А можно попасть только в И. N(И) = N(А) = 1.
• Д: Из А можно попасть только в Д. N(Д) = N(А) = 1.

3. Дальнейшие вершины:

• В: Можно попасть из Б. N(В) = N(Б) = 1.
• Ж: Можно попасть из И. N(Ж) = N(И) = 1.
• Г: Можно попасть из Д. N(Г) = N(Д) = 1.

4. Вершины с несколькими входящими путями:

• Е: Можно попасть из Б и Д. N(Е) = N(Б) + N(Д) = 1 + 1 = 2. (Важно: по условию нам нужно НЕ проходить через Е, поэтому эти пути мы учитывать не будем при дальнейшем расчете).
• К: Можно попасть из В и Ж. N(К) = N(В) + N(Ж) = 1 + 1 = 2.

5. Конечная вершина (Л):

• Можно попасть из Г и К.
• Пути из Г: N(Г) = 1.
• Пути из К: N(К) = 2.
• Важно: Мы не должны проходить через Е. Пути, ведущие к Е, не влияют на пути из А в Л, если они не проходят через Е.

Пересчитаем пути, исключая Е:

1. А: N(А) = 1

2. Б: N(Б) = 1

3. И: N(И) = 1

4. Д: N(Д) = 1

5. В: N(В) = N(Б) = 1

6. Ж: N(Ж) = N(И) = 1

7. Г: N(Г) = N(Д) = 1

8. К: N(К) = N(В) + N(Ж) = 1 + 1 = 2

9. Л: Можно попасть из Г и К. Мы не можем попасть в Л через Е, потому что все пути, ведущие в Е, уже исключены. Таким образом, мы должны суммировать пути, ведущие к Л из доступных вершин.

• Пути из Г: N(Г) = 1
• Пути из К: N(К) = 2
• Общее количество путей в Л = N(Г) + N(К) = 1 + 2 = 3.

Ответ: Существует 3 различных пути из пункта А в пункт Л, не проходящих через пункт Е.