СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 3 № 14764

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

 

П1П2П3П4П5П6П7
П145
П2129
П343
П4121710
П51713
П6510137
П7937

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта Г в пункт Д, если передвигаться можно только по указанным дорогам. В ответе укажите целое число – длину дороги в километрах.

ВНИМАНИЕ. Длины отрезков на схеме не отражают длины дорог.

Решение.

1) Д — единственная вершина, степень которой 4, значит, Д соответствует П6.

2) Можно заметить, что есть два населённых пунктов с тремя дорогами и четыре с двумя. Из этого можно сделать вывод: П4 и П7 это, либо Б, либо В, а населённые пункты П1, П3, П2 и П5 это Е, Г, А или К. Исходя из таблицы видно, что между П1 и П5 дороги нет, зато есть дорога, идущая вокруг Д(П6): П5—П4—П2—П7—П3—П1. Отсюда получаем: Е и К это, либо П5, либо П1. Из П5 есть дорога в П4, далее, в свою очередь есть дорога в Д(П6), а из П1 есть дорога в П3, но потом нет дороги в Д(П6).

3) Таким образом, П5 — К, П1 — Е. А если учесть цепочку П5—П4—П2—П7—П3—П1, то можно найти все оставшиеся: Г — П3, Б — П7, А — П2, В — П4.

Тогда ответ: кратчайший путь из Г в Д равен 9 км: Г(П3)—Е(П1)—Д(П6).

 

Ответ:9.