Задание №1 — Анализ матрицы смежности
На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 | |
| П1 | 12 | 13 | 24 | |||||
| П2 | 31 | 81 | ||||||
| П3 | 12 | 43 | ||||||
| П4 | 13 | 31 | ||||||
| П5 | 41 | 28 | 77 | |||||
| П6 | 24 | 41 | ||||||
| П7 | 81 | 28 | 19 | |||||
| П8 | 43 | 77 | 19 |
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта С в пункт F и из пункта D в пункт H. В ответе запишите целое число.
Правильный ответ
90
Пояснение
Решение:
Проанализировав граф, определим, что пункту H соответствует строка 1 (у этой вершины три соседа, каждый из которых имеет степень 2). Пункту E соответствует строка 2 (её соседи имеют степени 2 и 3). Общим смежным узлом для них является вершина D, обозначенная номером 4. Длина ребра между D и H составляет 13. Вторым соседом для E является вершина A под номером 7. У вершины A есть два соседа со степенью 3 — это пункты 5 и 8, путь между которыми равен 77.
Ответ: 90
Источник: ФИПИ