4. Тип 9 № 35586 На рисунке схема дорог, связывающих населенные пунк- ты А, В, С, D, E, F, G. По каждой дороге можно двигаться толь- ко в одном направлении, указанном стрелкой. Сколько суще- ствует различных путей из населенного пункта А в населенный пункт G?

Решение:

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

1. N(A) = 1 (исходный пункт).
2. N(B) = N(A) = 1.
3. N(C) = N(A) = 1.
4. N(D) = N(A) + N(C) = 1 + 1 = 2 (пути из А и из С).
5. N(E) = N(C) + N(D) = 1 + 2 = 3 (пути из С и из D).
6. N(F) = N(B) + N(E) = 1 + 3 = 4 (пути из B и из E).
7. N(G) = N(D) + N(E) + N(F) = 2 + 3 + 4 = 9 (пути из D, E, F).

Подробный подсчет:

N(A) = 1

N(B) = N(A) = 1

N(C) = N(A) = 1

N(D) = N(A) + N(C) = 1 + 1 = 2

N(E) = N(C) + N(D) = 1 + 2 = 3

N(F) = N(B) + N(E) = 1 + 3 = 4

N(G) = N(D) + N(E) + N(F) = 2 + 3 + 4 = 9

Ответ: 9