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