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