ЕГЭ Информатика 2020: Разбор задачи 3 (граф)

Условие задачи

На рисунке изображена схема дорог Омского района в виде графа. Таблица содержит среднюю протяженность каждой из этих дорог в километрах. Нумерация населенных пунктов в таблице не связана с буквенными обозначениями на графе. Необходимо определить протяженность дороги из пункта A в пункт E и записать в ответ целое число, как указано в таблице.

Решение задачи

Для решения задачи необходимо сопоставить номера населенных пунктов из таблицы с буквенными обозначениями на графе. Подсчитаем количество дорог, входящих в каждый пункт на графе и в таблице.

Таблица:

  • Пункт 1: 1 дорога
  • Пункт 2: 2 дороги
  • Пункт 3: 1 дорога
  • Пункт 4: 5 дорог
  • Пункт 5: 3 дороги
  • Пункт 6: 4 дороги
  • Пункт 7: 3 дороги

Граф:

  • Пункт A: 1 дорога
  • Пункт B: 4 дороги
  • Пункт C: 2 дороги
  • Пункт D: 5 дорог
  • Пункт E: 2 дороги
  • Пункт K: 3 дороги

Сравнивая данные, находим:

  • Пункт D (5 дорог) соответствует пункту 4 в таблице.
  • Пункт B (4 дороги) соответствует пункту 6 в таблице.

Остальные пункты пока не определены однозначно.

На графе два пункта имеют по две входящие дороги: E и C. Для определения, какой из них E, обратим внимание на связи: пункт E соединен с пунктом D (5 дорог, пункт 4 в таблице) и с пунктом K (3 дороги). Пункт C тоже связан с пунктом D. Однако, пункт E связан с пунктом K, в то время как пункт C – нет. Найдем в таблице пункт, имеющий три входящие дороги, который также связан с пунктом 4. Это пункт 7. Пункт 7 пересекается с пунктом 4 (D) и с пунктом 1. Поскольку пункт 1 также имеет одну входящую дорогу, то он соответствует пункту A. Пункт 7 соответствует пункту K. Таким образом, пункт 1 соответствует пункту E.

Теперь, зная соответствия, смотрим в таблице на пересечение пункта A (пункт 3 в таблице) и пункта E (пункт 1 в таблице). В условии задачи не указана нумерация в таблице, поэтому предположим, что в таблице номер пункта E — 1, а A — 3. На пересечении пунктов 1 и 3 стоит цифра 9. (В оригинальном тексте есть несоответствие в определении соответствия пунктов).

Протяженность дороги из пункта A в пункт E составляет 9 километров. (Предполагается, что в таблице указано значение 9 километров на пересечении соответствующих пунктов).

Что будем искать? Например,программа