Задание №1 — Анализ матрицы смежности
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| Номер пункта | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||
| Номер пункта | 1 | 16 | 17 | 18 | |||||
| 2 | 16 | 19 | 12 | ||||||
| 3 | 17 | 20 | 13 | ||||||
| 4 | 18 | 19 | 21 | 22 | 14 | 11 | |||
| 5 | 20 | 21 | 23 | 15 | |||||
| 6 | 22 | 23 | 10 | ||||||
| 7 | 13 | 14 | 15 | ||||||
| 8 | 12 | 11 | 10 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт В. В ответе запишите целое число так, как оно указано в таблице.
Правильный ответ
13
Пояснение
Решение:
Степени вершин схемы: A — 3, B — 3, C — 3, D — 3, E — 3, F — 3, G — 4, H — 6.
Число заполненных клеток в строках таблицы: 1 — 3, 2 — 3, 3 — 3, 4 — 6, 5 — 4, 6 — 3, 7 — 3, 8 — 3.
Степень 6 только у H и только у пункта 4, степень 4 только у G и только у пункта 5. Значит, H = 4 и G = 5.
Соседи G на схеме — это A, B, F и H. Соседи пункта 5 — это 3, 4, 6, 7; пункт 4 — это H, поэтому вершинам A, B, F отвечают пункты 3, 6 и 7.
Различим их: A соединена с B, C и G, то есть дороги в H у неё нет; а B и F с H соединены. В таблице у пункта 3 соседи 1, 5, 7 — пункта 4 среди них нет, значит, A = 3.
Осталось отличить B от F: B соединена с A, а F — нет. Соседи пункта 7 — это 3, 4, 5, и среди них есть 3 (то есть A), значит, B = 7 (а F = 6).
Дорога A—B — это клетка на пересечении строки 3 и столбца 7, она равна 13.
Ответ: 13