Задание №1 — Анализ матрицы смежности
На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
| Номер пункта | ||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | * | * | |||||
| 2 | * | * | ||||||
| 3 | * | * | ||||||
| 4 | * | * | * | |||||
| 5 | * | * | * | * | ||||
| 6 | * | * | * | |||||
| 7 | * | * |
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера в таблице могут соответствовать населённым пунктам F и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Правильный ответ
37
Пояснение
Решение:
Степени вершин схемы: A — 2, B — 2, C — 3, D — 4, E — 3, F — 2, G — 2.
Число звёздочек в строках таблицы: 1 — 2, 2 — 2, 3 — 2, 4 — 3, 5 — 4, 6 — 3, 7 — 2.
Степень 4 только у D и только у пункта 5, поэтому D = 5.
Вершин степени 2 четыре: A, B, F и G, им отвечают пункты 1, 2, 3 и 7. При этом A и B соединены с D, а F и G с D не соединены (F соединена с C и G, G — с E и F).
В таблице пункт 1 соединён с 5-м и 6-м, пункт 2 — с 4-м и 5-м, то есть оба соседствуют с пунктом 5; а пункты 3 (соседи 6 и 7) и 7 (соседи 3 и 4) с пунктом 5 не соединены.
Значит, A и B — это пункты 1 и 2, а вершинам F и G отвечают пункты 3 и 7. Записываем их в порядке возрастания.
Ответ: 37