9
Шешімі: Подсчёт путей в графе
ОГЭ · Информатика · Тапсырма 9 · Графы и пути
КүрделіФИПИ0e0BF6Қысқа жауап≈ 3 минутТалдау 5 қадамЖауап сверен с ключом
Условие
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешім по шагам
5 қадам1
Из города А есть один путь в город Б и один путь в город Г.
$$N(А)=1$$2
В город Б ведут пути из городов А и Г, а в город В — путь из города Г.
$$N(Б)=N(А)+N(Г)=2, N(В)=N(Г)=1$$3
В город Д ведут пути из городов Б и В, а в город Е — пути из городов Б и В?
4
По схеме: $N(Д)=N(Б)+N(В)=3$, $N(Е)=N(Г)+N(В)+N(Б)=3$.
В город Ж ведут дороги из городов Д и Е, поэтому складываем количество путей к этим вершинам.
$$N(Ж)=N(Д)+N(Е)=3+3=6$$Жауап
6
6
так ответ выглядит в бланкеГде здесь ошибаются
Считать дороги вместо полных путей.
Не учитывать разные варианты прохождения через промежуточные города.
Двигаться по дороге против направления стрелки.