Подсчёт путей в ориентированном графе
На рисунке — схема дорог, соединяющих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Ж? (Текст на фото сильно выцвел, условие прочитано по видимым фрагментам.)
Решение
Дороги по стрелкам: А→Б, А→В, Б→Г, В→Г, В→Д, Г→Д, Д→Е, Д→Ж, Е→Ж, Ж→З, Ж→И, З→К, И→К.
Пусть
Из Ж выходят дороги только в З и И, а дальше путь идёт в К. Значит, каждый путь из А в К проходит через Ж, и все
💡 Почему так
Число путей в вершину равно сумме чисел путей во все вершины, из которых в неё идут стрелки.
Ответ
✓ dzmen.ru
Помогло?
