Задание 3. Поиск кратчайшего пути: Демоверсия егэ по информатике 2020: объяснение и решение
*** КАНАЛ ЮТЬЮБ ***
ЕГЭ по информатике -> ЕГЭ 2020 -> ЕГЭ 2020
Разбор 3 задания. Демоверсия егэ по информатике 2020, ФИПИ:
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
|
|
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова протяжённость дороги из пункта Д в пункт Е.
В ответе запишите целое число – так, как оно указано в таблице.
📹 Видеоразбор демоверсии егэ 2020
✍ Решение:
- Выберем на граве вершины с уникальным количеством ребер: это вершина А — 1 ребро и вершина Д — 5 ребер. Найдем и обозначим их в таблице:
- Так как вершина А соединяется только с вершиной Б, то обозначим вершину Б тоже:
- Вершина Б соединяется с четырьмя вершинами, у которых разное количество ребер: А(1), В(2), Д(5) и Г(3). Раз количество ребер разное, то по таблице определим все эти вершины:
- Теперь для поиска протяженности пути от пункта Д в пункт Е достаточно найти вершину Е. По графу видим, что у нее 2 ребра. Из оставшихся столбцов и строк таблицы, находим строку с двумя значениями:
- Таким образом, вершине Д соответствует строка/столбец 4, а вершине, Е — 1. На пересечении их в таблице стоит число 9.
Результат: 9