Задание №1 — Анализ матрицы смежности
На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | 19 | 17 | 10 | 14 | |||
| П2 | 19 | 10 | |||||
| П3 | 17 | 21 | |||||
| П4 | 10 | 21 | 19 | 18 | |||
| П5 | 19 | ||||||
| П6 | 18 | ||||||
| П7 | 14 | 10 |
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта А в пункт В и из пункта К в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.
Правильный ответ
31
Пояснение
Решение:
Обратим внимание, что у пункта А есть два соседа, степень которых равна 4. Это позволяет однозначно определить, что А соответствует номеру 3. Оставшиеся два пункта со степенью 2 (это К и Д) могут соотноситься с номерами 2 и 7 в произвольном порядке (при этом длина ребра между ними всегда равна 10). Их общим смежным пунктом является Г, имеющий номер 1. Исходя из этого, пункту В соответствует номер 4. Следовательно, протяженность дороги между А и В составляет 21.
Ответ: 31
Источник: ФИПИ