Question

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути между пунктами В и К. Передвигаться можно только по указанным дорогам.

Answer 1

Только из пункта П2 выходят 4 дороги, следовательно, П2 соответствует вершине В.  П2 соединен с П1, П3, П4, П7.  Из них из П3  выходят 3 дороги, следовательно, П3 - это вершина Г.

Осталось П1 и П7 - А и Б.  Подходят оба варианта по графу.  П1 - это А и П7 - это Б, или П7 - это А и П1 - это Б.  Выберем первый вариант.

Осталась одна дорога из П2 в П4 - это вершина Д.  Из П4 выходят две дороги в П2 и П6, следовательно, П6 - это Е.  Остался последний пункт П5,  он соответствует вершине К.

Получили следующую таблицу:

А -> П1

Б -> П7

В -> П2

Г - > П3

Д -> П4

Е - > П6

К - > П5

Первый путь: В - Г - К = 10 + 20 + 30

Второй путь:  В - Д - Е - К = 5 + 10 + 10 + 25

Третий путь: В - Г - Е - К = 10 + 15 + 10 = 35

Тогда кратчайший путь от В до К будет:  5 + 10+10 = 25