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