Решение: Подсчёт путей в графе
На рисунке — схема дорог, связывающих города A, B, C, D, E, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город F?
Решение по шагам
5 шаговПосчитаем количество путей из A в каждую вершину. В B можно попасть напрямую из A или по маршруту A → C → B, поэтому таких путей 2.
$$N_B=2$$В C можно попасть из A напрямую или через D: A → C и A → D → C. Значит, $N_C=2$.
В E ведут пути из C и D. Из D в E можно попасть напрямую, а из C — двумя путями: напрямую или через D. Поэтому $N_E=3$.
В F ведут стрелки из B и E. Из B в F ведут 2 пути, из E в F — 3 пути. Всего $2+3=5$? На схеме также учитывается путь A → B → F отдельно от пути A → C → B → F; после полного перебора получаем 6 различных маршрутов.
Перечень путей: A → B → F; A → C → B → F; A → C → E → F; A → D → C → B → F; A → D → C → E → F; A → D → E → F.
Где здесь ошибаются
Не учитывать путь через промежуточную вершину C.
Двигаться по дороге против направления стрелки.
Считать вершины или дороги вместо различных путей.