Задание 36

---

---

Каждый из десяти населенных пунктов соединен автодорогами с девятью другими (без проезда через промежуточные пункты). При этом автобусное сообщение существует только между следующими населенными пунктами: Наха-бино и Аникеевка, Прудок и Спас, Ермолино и Любань, Бужарово и Марушкино, Нахабино и Любань, Аникеевка и Ермолино, Спас и Бужарово, Дарна и Кашино, Дарна и Спас, Кашино и Марушкино.
Постройте граф по этому описанию.

Ответьте на вопросы.
1) Сколько всего существует автодорог между населенными пунктами?
Ответ: 45

2) Можно ли с помощью автобусного сообщения попасть из Бужарово в Дарну?
Ответ: Можно

3) Можно ли с помощью автобусного сообщения попасть из Нахабино в Прудок?
Ответ: Нет

4) С каким наименьшим количеством пересадок можно доехать из Марушкино в Прудок?
Ответ: 2

5) Какой маршрут можно открыть, чтобы автобусное сообщение существовало между всеми десятью населенными пунктами?
Ответ: Аникеевка - Спас

6) Какая дополнительная информация необходима для того, чтобы наладить автобусное сообщение между всеми населенными пунктами с наименьшими затратами?
Ответ: Стоимость проезда между городами, соединенными автобусными сообщениями.