Решение: Сопоставление схемы дорог и таблицы
На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам E и G на схеме.
| Номер пункта | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | * | * | |||||
| 2 | * | * | * | * | |||
| 3 | * | * | |||||
| 4 | * | * | * | ||||
| 5 | * | * | * | ||||
| 6 | * | * | * | ||||
| 7 | * | * | * |
Запишите два номера в возрастающем порядке без пробелов и знаков препинания.
Решение по шагам
3 шагаПредставим схему дорог в виде неориентированного графа. Звёздочки в строке таблицы показывают населённые пункты, непосредственно соединённые дорогами с данным пунктом.
Для каждой вершины схемы сравниваем количество дорог и взаимное расположение её соседей с соответствующей строкой таблицы. Такое сопоставление однозначно устанавливает соответствия между вершинами схемы и номерами пунктов.
При проверке вершин E и G получаем номера 4 и 5 соответственно.
Где здесь ошибаются
Считать таблицу ориентированной и учитывать только строки без проверки симметричных связей.
Сравнивать только количество дорог, не учитывая связи соседних вершин.
Записать номера с пробелом или знаком препинания.