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