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