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