Тип 1 № 68263 
Анализ информационных моделей. Неоднозначное соотнесение таблицы и графа
i
На рисунке схема дорог изображена в виде графа, в таблице указано время в пути (в минутах) по каждой дороге. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите минимальное время перемещения по данным дорогам из пункта И в пункт Д. В ответе укажите целое число: минимальное время в минутах.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 | П9 |
| П1 | | 20 | | | 24 | 34 | 44 | | |
| П2 | 20 | | | | | | 23 | | |
| П3 | | | | 35 | | 37 | 26 | | 50 |
| П4 | | | 35 | | | | | 32 | 38 |
| П5 | 24 | | | | | 21 | | | |
| П6 | 34 | | 37 | | 21 | | | 25 | |
| П7 | 44 | 23 | 26 | | | | | | |
| П8 | | | | 32 | | 25 | | | |
| П9 | | | 50 | 38 | | | | | |
Решение. Заметим, что в таблице имеются четыре населенных пункта степени 2, два населенных пункта степени 3 и три населенных пункта степени 4.
Населенный пункт Ж — единственный пункт степени 2, который обе дороги имеет с пунктами степени 4. Ему соответствует пункт П5.
Из двух пунктов степени 3 только пункт Б имеет дороги с двумя пунктами степени 2, это пункт Б, и ему соответствует пункт П4. Следовательно, населенному пункту Е соответствует пункт П7.
Поскольку Е имеет дорогу с пунктом К, то пункту К соответствует населенный пункт П2. Тогда населенный пункт И соответствует пункту П1. Пункт Г связан с пунктами Ж (П5) и И (П1), следовательно, это населенный пункт П6. Тогда населенный пункт Д — это пункт П3.
Пункт А имеет общие дороги с пунктами Г (П6) и Б (П4), следовательно, это пункт П8. Следовательно, населенный пункт В соответствует пункту П9.
Поскольку требуется найти кратчайшую (по времени) дорогу из пункта И в пункт Д, рассмотрим варианты маршрута.
1. Дорога И–Г–Д, или П1–П6–П3, время в пути 34 + 37 = 71 (мин.).
2. Дорога И–Е–Д, или П1–П7–П3, время в пути 44 + 26 = 70 (мин.).
3. Дорога И–Ж–Г–Д, или П1–П5–П6–П3, время в пути 24 + 21 + 37 = 82 (мин.).
4. Дорога И–К–Е–Д, или П1–П2–П7–П3, время в пути 20 + 23 + 26 = 69 (мин.).
Остальные маршруты больше по времени.
Минимальное время перемещения по дорогам из пункта И в пункт Д составляет 69 минут.
Ответ: 69.
Ответ: 69