Задание 59 ГДЗ Семенов Рудченко 6 класс (Информатика)

59. Рассмотри граф, представляющий схему дорог от дома, где живёт Коля, до школы. Нарисуй дерево перебора возможных маршрутов от дома Коли до школы. В качестве элементов такого дерева используй имена вершин графа. Через каждую точку можно проходить не больше одного раза, по дорогам со стрелками можно двигаться только в направлении стрелок. Какой путь оказался самым коротким?

Переберём все возможные маршруты от дома Коли до школы, не проходя через одну и ту же вершину дважды и двигаясь по стрелкам.

Получаются такие пути с их длинами:

• $$ДАЕЖШ = 8$$
• $$ДБЖШ = 9$$
• $$ДГАШ = 9$$
• $$ДВГШ = 9$$
• $$ДАЕЖШ = 8$$

Сравниваем длины маршрутов. Наименьшая длина равна $$8$$.

Ответ

Самый короткий путь: $$ДАЕЖШ$$, его длина равна $$8$$.