Шешімі: Пути через заданный город
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Л?
Шешім по шагам
3 қадамТак как все дороги имеют направление, количество путей до каждой вершины удобно считать последовательно: число путей в вершину равно сумме чисел путей в её предшественники.
$$N(X)=\sum N(P_i)$$Путь из А в М, проходящий через Л, состоит из двух независимых частей: пути из А в Л и пути из Л в М. Поэтому их количества перемножаются.
$$N_{A\to M\ через\ Л}=N_{A\to Л}\cdot N_{Л\to M}$$Подсчёт по схеме дорог даёт итоговое количество путей, равное 27.
Где здесь ошибаются
Складывают пути из А в Л и из Л в М вместо перемножения.
Учитывают пути из А в М, которые не проходят через город Л.
Игнорируют направления дорог.