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