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