Решение: Пути через заданную вершину
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город К?
Решение по шагам
3 шагаДля каждой вершины ориентированного графа последовательно подсчитывают количество путей из исходной вершины, складывая количества путей во всех предшествующих вершинах.
Отдельно подсчитывают число путей из А в К и число путей из К в М. Каждый путь из А в М, проходящий через К, однозначно раскладывается на эти две части.
Перемножив полученные количества путей, получают общее число маршрутов через К.
$$N_{A\to M\text{ через }K}=N_{A\to K}\cdot N_{K\to M}=27$$Где здесь ошибаются
Считать все пути из А в М, не проверяя прохождение через К.
Складывать вместо умножения число путей до К и после К.
Учитывать дороги как двусторонние, хотя движение возможно только по стрелкам.