Упр.3.36 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

Задача

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

Подробный ответ

Обозначим населённые пункты первыми буквами их названий: Н, А, П, С, Е, Л, Б, М, Д, К.

Автодороги образуют полный граф: каждый пункт соединён с девятью другими, значит число автодорог равно половине суммы степеней всех вершин:

$$\frac{10 \cdot 9}{2} = 45.$$

Автобусные маршруты задают рёбра графа:

Н–А, П–С, Е–Л, Б–М, Н–Л, А–Е, С–Б, Д–К, Д–С, К–М.

По этому графу:

из Бужарово в Прудок можно доехать по маршруту Б–С–П;
из Нахабино в Прудок по автобусным маршрутам попасть нельзя;
из Марушкино в Прудок кратчайший путь: М–Б–С–П, то есть 2 пересадки;
чтобы автобусное сообщение стало возможным между всеми десятью пунктами, достаточно добавить, например, маршруты Н–М, А–С, Б–Л;
для организации сообщения с наименьшими затратами нужна дополнительная информация о стоимости билетов.