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