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