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