Алгоритм нахождения путей в графе. На рисунке изображена схема дорог, соединяющих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Из А в Г идут ... дорог(и).
Из Г в К идут ... дорог(и).
Количество дорог из А в К = количество дорог из А в Г × количество дорог из Г в К = ... × ... = ...
Фото плохо читается, поэтому схему считаю такой: А→Б, А→В, А→Д, Б→В, Б→Г, В→Г, В→Е, Г→Е, Г→Ж, Д→Е, Д→И, Е→Ж, Е→И, Ж→К, И→К.
Из А в Г. Пусть
Пути: А–Б–Г, А–Б–В–Г, А–В–Г. Через Д в Г попасть нельзя.
Из Г в К. Пусть
Пути: Г–Ж–К, Г–Е–Ж–К, Г–Е–И–К.
Из А в К через Г:
Каждый путь из А в Г можно продолжить любым путём из Г в К, поэтому числа путей на участках перемножаются (правило произведения).
Из А в Г идут
Из Г в К идут
Количество дорог из А в К =
