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