Решение: Подсчёт путей в графе
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение по шагам
5 шаговРассмотрим пути, начинающиеся переходом из города А в город Б.
$$4$$Из города Б можно попасть в К напрямую, через В, через Д. Через В возможны два продолжения: сразу в К или через Е в К. Итого из Б в К ведут 4 пути.
$$1 + 1 + 1 + 1 = 4$$Из города А в город В можно попасть напрямую. Далее есть два пути: сразу в К или через Е в К.
$$2$$Из города А в город Г можно попасть одним способом, затем следует путь Г → Е → К.
$$1$$Складываем количества путей по трём возможным первым переходам из А.
$$4 + 2 + 1 = 7$$Где здесь ошибаются
Не учитывают путь через город Д.
Считают только непосредственные дороги в город К, не рассматривая промежуточные города.
Повторно считают один и тот же путь.