Шешімі: Подсчёт путей в дорожной схеме
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М?
Шешімін қадамдап көрсету
4 қадамПредставим схему дорог в виде ориентированного графа: города являются вершинами, а дороги — направленными рёбрами.
Обозначим через $f(X)$ количество путей из города А в город X. Для города А принимаем $f(А)=1$ — это начальная точка маршрута.
Для каждого следующего города подсчитываем сумму значений $f$ для всех городов, из которых в него ведут дороги: $f(X)=\sum f(Y)$.
Последовательно применяя это правило к вершинам схемы, получаем для города М значение $f(М)=33$.
Где здесь ошибаются
Считать дороги, а не полные маршруты.
Учитывать движение против направления стрелок.
Не складывать пути, приходящие в город из разных предшествующих городов.