Упр.3.41 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

Шесть торговых точек А, Б, В, Г, Д, Е соединены дорогами с односторонним движением (направление движения указано стрелками, протяжённость дорог в км — числами). Необходимо перевезти груз из точки А в точку Е. Ответьте на вопросы. Для решения задачи постройте и проанализируйте дерево.

1. Сколько существует различных вариантов маршрута?
2. Какой маршрут самый короткий?
3. Какой маршрут следует выбрать, чтобы по пути посетить все торговые точки?

По схеме получаем все возможные маршруты из точки А в точку Е:

• А → Г → Д → В → Е
• А → Б → Г → Д → В → Е
• А → Б → Д → В → Е
• А → Б → В → Е

Итак, всего существует 4 различных маршрута.

Сравним их длины:

• А → Г → Д → В → Е: $$3+5+5+7=20$$ км
• А → Б → Г → Д → В → Е: $$5+6+5+5+7=28$$ км
• А → Б → Д → В → Е: $$5+3+5+7=20$$ км
• А → Б → В → Е: $$5+7+7=19$$ км

Самый короткий маршрут — А → Б → В → Е, его длина $$19$$ км.

Чтобы по пути посетить все торговые точки, нужно выбрать маршрут, проходящий через все вершины:

А → Б → Г → Д → В → Е.

Ответ: 1) 4; 2) А → Б → В → Е; 3) А → Б → Г → Д → В → Е.