Упр.36 ГДЗ Рабочая тетрадь Босова 9 класс (Информатика)
Каждый из десяти населённых пунктов соединён автодорогами с девятью другими (без проезда через промежуточные пункты). При этом автобусное сообщение существует только между следующими населёнными пунктами: Нахабино и Аникеевка, Прудок и Спас, Ермолино и Любань, Бужарово и Марушкино, Нахабино и Любань, Аникеевка и Ермолино, Спас и Бужарово, Дарна и Кашино, Дарна и Спас, Кашино и Марушкино.
Постройте граф по этому описанию. Обозначьте населённые пункты первыми буквами их названий. Существующие автодороги обозначьте пунктирной линией, автобусные — сплошной. Ответьте на вопросы.
- Сколько всего существует автодорог между населёнными пунктами?
- Можно ли с помощью автобусного сообщения попасть из Бужарово в Дарну?
- Можно ли с помощью автобусного сообщения попасть из Нахабино в Прудок?
- С каким наименьшим количеством пересадок можно доехать из Марушкино в Прудок?
- Какой маршрут можно открыть, чтобы автобусное сообщение существовало между всеми десятью населёнными пунктами?
- Какая дополнительная информация необходима для того, чтобы наладить автобусное сообщение между всеми населёнными пунктами с наименьшими затратами?
Обозначим населённые пункты первыми буквами их названий: Н — Нахабино, А — Аникеевка, П — Прудок, С — Спас, Е — Ермолино, Л — Любань, Б — Бужарово, М — Марушкино, Д — Дарна, К — Кашино.
Автодороги соединяют каждый пункт с девятью другими, значит граф полный. Тогда число автодорог равно:
$$\frac{10 \cdot 9}{2} = 45.$$
Автобусные маршруты заданы рёбрами:
$$НА,\; ПС,\; ЕЛ,\; БМ,\; НЛ,\; АЕ,\; СБ,\; ДК,\; ДС,\; КМ.$$
По этим маршрутам:
- из Бужарово в Дарну попасть можно: $$Б \to С \to Д$$;
- из Нахабино в Прудок попасть нельзя, так как эти вершины лежат в разных автобусных связных компонентах;
- из Марушкино в Прудок с наименьшим числом пересадок можно доехать за 2 пересадки: $$М \to Б \to С \to П$$;
- чтобы автобусное сообщение существовало между всеми десятью населёнными пунктами, достаточно открыть маршрут $$А — С$$;
- для организации автобусного сообщения с наименьшими затратами нужна дополнительная информация о стоимости проезда по каждому маршруту.
Ответ
1) $$45$$.
2) Да.
3) Нет.
4) $$2$$ пересадки: $$М \to Б \to С \to П$$.
5) $$А — С$$.
6) Стоимость билетов за проезд в автобусах.
