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


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

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

 

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, то ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Из­вест­но, что длина крат­чай­ше­го пути из пунк­та A в пункт E не пре­вы­ша­ет 30 ки­ло­мет­ров. Опре­де­ли­те длину крат­чай­ше­го пути из пунк­та Г в пункт K. В от­ве­те ука­жи­те целое число — длину пути в ки­ло­мет­рах.

Решение.

1. Д — единственная вершина степени 4, у которой нет дорог к населённым пунктам А и Г, значит, Д соответствует пункту П7.

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

3. Предположим, что П5 это А, а П3 это К. Из этого можно сделать вывод: П4 это Г, П2 это Е, П1 это В, а П6 это Б. После этого находим кратчайший путь между вершинами А и Е, который будет равен 27, что соответствует условию задания. Значит, предположение оказалось верным.

4. Далее находим кратчайший путь между вершинами Г и К, который будет равен 49.

 

Ответ: 49.