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