Шешімі: Количество путей в графе
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Шешім по шагам
5 қадамОбозначим количество путей из А до каждой вершины. Для городов Б, В и Д существует по одному пути из А.
$$N_{Б}=1,\quad N_{В}=1,\quad N_{Д}=1$$В город Е ведут дороги из Б и В, поэтому количество путей до Е равно двум.
$$N_{Е}=N_{Б}+N_{В}=1+1=2$$В город Г ведут дороги из А, В и Д, поэтому количество путей до Г равно трём.
$$N_{Г}=1+N_{В}+N_{Д}=1+1+1=3$$В город Ж ведут дороги из Г и Д, поэтому количество путей до Ж равно четырём.
$$N_{Ж}=N_{Г}+N_{Д}=3+1=4$$В город К можно попасть непосредственно из В, из Е или из Ж. Складываем количества путей по этим направлениям.
$$N_{К}=N_{В}+N_{Е}+N_{Ж}=1+2+4=7$$Где здесь ошибаются
Не учитывать прямой путь из В в К.
Считать города, а не различные маршруты.
Забыть сложить пути, ведущие в К через Е и Ж.