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