Решение: Количество путей в графе
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Схема дорог между городами. Саму картинку ещё готовим — у остальных задач темы она на месте.
Решение по шагам
4 шагаИз города А можно попасть в Б, В и Г непосредственно. Поэтому количество путей до этих вершин равно 1, 1 и 1 соответственно.
$$N(Б)=1,\quad N(В)=1,\quad N(Г)=1$$В город В ведут дороги из А, Б и Г. Поэтому количество путей до В равно 3.
$$N(В)=1+1+1=3$$В город Д ведут дороги из Б и В, а в город Е — из Г и В.
$$N(Д)=N(Б)+N(В)=1+3=4,\quad N(Е)=N(Г)+N(В)=1+3=4$$В город К можно попасть из В, Д или Е. Складываем количество путей до этих вершин.
$$N(К)=N(В)+N(Д)+N(Е)=3+4+4=11$$Где здесь ошибаются
Не учитывают пути, проходящие через промежуточную вершину В.
Считают дороги вместо различных путей.
Забывают, что в К ведут три дороги: из В, Д и Е.