Задание №1 — Анализ матрицы смежности
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| Номер пункта | ||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | 3 | 6 | |||||
| 2 | 3 | 4 | 7 | |||||
| 3 | 8 | 1 | 11 | |||||
| 4 | 8 | 2 | 10 | |||||
| 5 | 6 | 4 | 1 | 2 | 5 | |||
| 6 | 11 | |||||||
| 7 | 7 | 10 | 5 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяженность дороги из пункта Д в пункт К. В ответе запишите целое число — так, как оно указано в таблице.
Правильный ответ
10
Пояснение
Решение:
Степени вершин схемы: А — 2, Б — 3, В — 1, Г — 5, Д — 3, Е — 3, К — 3.
Число заполненных клеток в строках таблицы: 1 — 2, 2 — 3, 3 — 3, 4 — 3, 5 — 5, 6 — 1, 7 — 3.
Однозначно определяются три вершины: Г = 5 (единственная степень 5), В = 6 (единственная степень 1), А = 1 (единственная степень 2).
Дальше идём по цепочке:
- Е — единственный сосед В. У пункта 6 единственный сосед — 3, значит, Е = 3.
- Соседи Е на схеме — это В, Г и К. Соседи пункта 3 — это 4, 5 и 6; пункты 5 и 6 уже заняты (Г и В), поэтому К = 4.
- Соседи К на схеме — Г, Д и Е. Соседи пункта 4 — это 3, 5 и 7, откуда Д = 7.
- Оставшийся пункт 2 — это Б (проверка: его соседи 1, 5, 7 — это А, Г, Д, как и на схеме).
Дорога Д—К — это клетка на пересечении строки 7 и столбца 4, она равна 10.
Ответ: 10