4. Графы: кратчайший путь и количество путей На рисунке — схема дорог, связывающих города А, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном указанном направлении, стрелкой. Сколько существует различных путей из города А в город G?

Решение:

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

1. Город А: Из города А можно попасть только в города B и D. Количество путей в город А равно 1 (сам город).
2. Город B: Из города А ведёт 1 путь в город B.
3. Город D: Из города А ведёт 1 путь в город D.
4. Город C: В город C можно попасть только из города B. Таким образом, количество путей в город C равно количеству путей в город B, то есть 1.
5. Город E: В город E можно попасть из городов B, C и D. Количество путей в город E равно сумме путей во все города, из которых в него ведут дороги: \( 1 \) (из B) + \( 1 \) (из C) + \( 1 \) (из D) = \( 3 \) пути.
6. Город F: В город F можно попасть из города D. Количество путей в город F равно количеству путей в город D, то есть 1.
7. Город G: В город G можно попасть из городов E и F. Количество путей в город G равно сумме путей во все города, из которых в него ведут дороги: \( 3 \) (из E) + \( 1 \) (из F) = \( 4 \) пути.

Ответ: Существует 4 различных пути из города А в город G.