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