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