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