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