Упр.3.36 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)
Решение #1
Рассмотрим вариант решения задания из учебника Босова, Аквилянов 9 класс, Просвещение:
3.36. Каждый из десяти населенных пунктов соединен автодорогами с девятью другими (без проезда через промежуточные пункты). При этом автобусное сообщение существует только между следующими населенными пунктами: Нахабино и Аникеевка, Прудок и Спас, Ермолино и Любань, Бужарово и Марушкино, Нахабино и Любань, Аникеевка и Ермолино, Спас и Бужарово, Дарна и Кашино, Дарна и Спас, Кашино и Марушкино.
Постройте граф по этому описанию.
Населенные пункты обозначены первыми буквами их названий.
Существующие автодороги обозначим пунктирной линией, автобусные сплошной.
Ответьте на следующие вопросы.
1) Сколько всего существует автодорог между населенными пунктами?
Количество автодорог равно количеству ребер в графе. Количество ребер вдвое меньше сумме степеней вершин. Каждая вершина имеет 9 путей (индекс, степень) в другие вершины. Количество автодорог = 9*10/2 = 45.
2) Можно ли с помощью автобусного сообщения попасть из Бужарово в Прудок?
Можно Б – С – П.
3) Можно ли с помощью автобусного сообщения попасть из Нахабино в Прудок?
Нельзя.
4) С каким наименьшим количеством пересадок можно доехать из Марушкино в Прудок?
2-е пересадки: М – Б – С – П
5) Какой маршрут можно открыть, чтобы автобусное сообщение существовало между всеми десятью населенными пунктами?
Несколько вариантов: Н – М, А – С, Б – Л.
6) Какая дополнительная информация необходима для того, чтобы наладить автобусное сообщение между всеми населенными пунктами с наименьшими затратами?
Стоимость билетов.
Популярные решебники 9 класс Все решебники
*К сожалению, временные проблемы с публикацией комментариев с мобильных устройств.