Задание 1 Вариант 3 Контрольная работа 2 ГДЗ Рабочая тетрадь Босова 11 класс (Информатика)

1. На рисунке схема дорог Н-ского района изображена в виде графа, а в таблице содержатся сведения о длинах этих дорог (в километрах). Таблицу и схему рисовали независимо друг от друга, поэтому нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути между пунктами В и Д. Передвигаться можно только по указанным дорогам.
Пункт В имеет 5 связей, других таких нет. В таблице это П6
Пункт Е имеет 4 связи, в таблице это П4.
Пункты В и Е имеют общие связи в пунктами Д и Г, Г имеет 3 связи, в таблице это П2, а Д это П7
К в таблице это П1, т.к. он имеет связь и с П2(Г), и с П4 (Е)
ВД=45
ВЕД=20+15=35
Ответ: 35

Сопоставим вершины графа с пунктами таблицы по числу связей.

Пункт В имеет 5 связей, и такой пункт в таблице один — это П6.

Пункт Е имеет 4 связи, значит это П4.

У пунктов В и Е общие соседние пункты — Д и Г. Из них Г имеет 3 связи, значит это П2, а Д — П7.

Тогда оставшийся пункт К — это П1, так как он соединён с П2 и П4.

По таблице длина дороги между В и Д равна 45 км. Проверим путь через Е:

$$ВЕ = 20,\quad ЕД = 15,\quad ВЕ + ЕД = 20 + 15 = 35$$

Значит, кратчайший путь между пунктами В и Д равен 35 км.

Ответ

35