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