Решение: Подсчёт путей в графе

ОГЭ · Информатика · Задание 9 · Графы и пути

ПовышеннаяФИПИ33203DКороткий ответ≈ 3 минутыРазбор в 2 шагаОтвет сверен с ключом

Условие

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Открыть задачу и решить самому

Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.

К подсказкам

Решение по шагам

2 шага

Из города А начинаются пути через города Б, В и Г. Перечислим все маршруты, которые заканчиваются в городе К.

После учёта направлений стрелок и исключения повторных маршрутов получаем шесть различных путей из А в К.

Ответ

так ответ выглядит в бланке

Где здесь ошибаются

Учитывать движение по дороге в направлении, противоположном стрелке.

Посчитать один и тот же путь несколько раз.

Принять промежуточную вершину за конечную.

Закрепить приёмВ теме «Графы и пути» ещё 170 задач — с ответом и таким же разбором.

Тренироваться

ПредыдущаяКоличество путей в графеСледующаяКоличество путей в графе

Как решать задание 9 ОГЭ, информатика

Разбор этой задачи разложен на 2 шага: видно, откуда берётся каждое число и где теряется балл. Ответ приведён рядом с выкладками, а не вместо них.

Задача из темы «Графы и пути»: в ней 171 задача, и у каждой есть такой же разбор. Регистрация не нужна.