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