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