Упр.36 ГДЗ Рабочая тетрадь Босова 9 класс (Информатика)

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

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

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

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

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

$$НА,\; ПС,\; ЕЛ,\; БМ,\; НЛ,\; АЕ,\; СБ,\; ДК,\; ДС,\; КМ.$$

По этим маршрутам:

1. из Бужарово в Дарну попасть можно: $$Б \to С \to Д$$;
2. из Нахабино в Прудок попасть нельзя, так как эти вершины лежат в разных автобусных связных компонентах;
3. из Марушкино в Прудок с наименьшим числом пересадок можно доехать за 2 пересадки: $$М \to Б \to С \to П$$;
4. чтобы автобусное сообщение существовало между всеми десятью населёнными пунктами, достаточно открыть маршрут $$А — С$$;
5. для организации автобусного сообщения с наименьшими затратами нужна дополнительная информация о стоимости проезда по каждому маршруту.

Ответ

1) $$45$$.
2) Да.
3) Нет.
4) $$2$$ пересадки: $$М \to Б \to С \to П$$.
5) $$А — С$$.
6) Стоимость билетов за проезд в автобусах.