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