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