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