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