Задание EGEINF1A48C1: Графы, таблицы и маршруты

Решение.
В таблице одна и та же перевозка записана дважды: в строке первого пункта и столбце второго, а также в симметричной клетке. Поэтому каждую дорогу учитываем один раз. Буквы на схемах уже заданы, перенумеровывать вершины не нужно.
Пустая клетка означает, что прямой дороги между соответствующими станциями нет. Совпадение лишь формы рисунка недостаточно: должны совпадать и пары соединённых пунктов, и стоимость каждого переезда.
Из таблицы получаем дороги: A–B — 2; A–C — 4; A–E — 1; B–C — 2; D–E — 3.
Всего должно быть 5 дорог. Все остальные пары различных букв должны остаться без прямого соединения.
Схема 1 не подходит: для A–E таблица задаёт стоимость 1, а на схеме эта дорога отсутствует.
Схема 2 не подходит: для A–B таблица задаёт стоимость 2, а на схеме указана стоимость 4.
Схема 3 подходит: A–B=2; A–C=4; A–E=1; B–C=2; D–E=3. Других дорог на ней нет.
Схема 4 не подходит: для A–E таблица задаёт стоимость 1, а на схеме эта дорога отсутствует.
Проверка: у выбранной схемы набор соседей каждой станции и все веса рёбер совпадают с соответствующей строкой таблицы. Симметричные клетки тоже совпадают, поскольку перевозки заданы между соседними станциями без выделения направления.
Все четыре варианта рассмотрены. У трёх найдено конкретное противоречие, у оставшегося проверен полный набор дорог. Значит, выбираем единственную подходящую схему под номером 3.
Ответ: 3.