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