Задание №1. Сопоставление графа и таблицы
Соответствие букв и номеров, различение похожих вершин и запись ответа: от простого примера к более сложным схемам.
Один и тот же пункт в задании №1 обозначен на схеме буквой, а в таблице номером. Соответствие между ними неизвестно, но связи сохраняются: если из пункта выходят три дороги, у его номера в таблице тоже должно быть три связи. Число дорог, соседние пункты и связи между ними помогают установить нужные соответствия и найти требуемую длину или номера пунктов.
Что дано и что требуется найти
Схема показывает, какие пункты соединены непосредственно. В таблице строка и столбец задают пару пунктов, а ячейка сообщает о дороге между ними. Число может обозначать её длину; звёздочка показывает только наличие дороги. Пустые ячейки и прочерки читаются по условию.
По требуемому ответу можно выделить несколько групп:
| Вопрос | Действие после сопоставления |
|---|---|
| Длина одной дороги ↗ | Найти ячейку на пересечении номеров её концов |
| Сумма длин нескольких дорог ↗ | Найти каждую указанную дорогу и сложить длины |
| Номера пунктов ↗ | Записать номера в порядке, указанном в условии |
Ссылки в таблице ведут к конкретным заданиям. Это ориентиры для разбора, а не полный перечень возможных формулировок. Даже внутри одной группы различаются устройство схемы, дополнительные сведения и порядок записи ответа.
Сопоставление на примере
Условие. Схема и таблица описывают одну сеть двусторонних дорог. Требуется определить длину дороги BC. Буквы на схеме латинские; длины в таблице указаны в километрах. Прочерк означает отсутствие прямой дороги.
| Пункт | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | - | - | - | 12 | - | - |
| 2 | - | - | - | 7 | 8 | 9 |
| 3 | - | - | - | - | 4 | - |
| 4 | 12 | 7 | - | - | - | 5 |
| 5 | - | 8 | 4 | - | - | - |
| 6 | - | 9 | - | 5 | - | - |
Число дорог у каждого пункта
Пункт на схеме называется вершиной, дорога между двумя пунктами ребром. Число рёбер у вершины называется её степенью. Соседи соединены одним ребром, без промежуточного пункта.
| Вершины схемы | Степень | Подходящие номера |
|---|---|---|
| A, B | 3 | 2, 4 |
| C, E | 2 | 5, 6 |
| D, F | 1 | 1, 3 |
Например, в строке 4 три числа: дороги ведут к пунктам 1, 2 и 6. Степень равна 3, независимо от значений 12, 7 и 5. Пока для A подходят оба номера, 2 и 4: одного совпадения степеней недостаточно.
Различение вершин по соседям
У D и F по одной дороге, но их соседи различаются. D соединён с A степени 3. Из номеров 1 и 3 подходит только 1: его сосед 4 имеет степень 3. Значит, D = 1 и A = 4.
F соединён с E степени 2. В таблице номер 3 соединён с номером 5 степени 2. Значит, F = 3 и E = 5. Для B из номеров 2 и 4 остаётся 2, поскольку номер 4 уже соответствует A. Для C из номеров 5 и 6 остаётся 6, поскольку номер 5 уже соответствует E.
Соответствие: A = 4, B = 2, C = 6, D = 1, E = 5, F = 3.
Проверка и ответ
После замены букв номерами дороги AB, AC, AD, BC, BE, EF превращаются в связи 4-2, 4-6, 4-1, 2-6, 2-5, 5-3. В таблице есть ровно эти шесть дорог. Отсутствующие связи тоже сохраняются: например, A и E не соединены, и в ячейке 4-5 стоит прочерк.
Концы дороги BC получили номера 2 и 6. На пересечении строки 2 и столбца 6 находится число 9. Ответ: 9.
Изменение вопроса и формата ответа
Сумма длин AD и EF. В ячейках 4-1 и 5-3 указаны 12 и 4. Сумма равна 16. Ячейки 4-1 и 1-4 описывают одну двустороннюю дорогу, поэтому повторно её длина не учитывается.
Номера C и F. Получено C = 6, F = 3. При требовании записать номера по возрастанию ответ 36. Если сначала требуется номер C, затем номер F, ответ 63. В обоих случаях разделители отсутствуют только тогда, когда этого требует условие.
Более сложные схемы
Начальной опорой может служить вершина, чья степень не повторяется у других вершин. Если такой вершины нет, сравниваются степени соседей. Когда совпадает и этот признак, помогают связи между соседями, цепочки и связи с уже определёнными пунктами.
В этой схеме у A и D по три дороги; степени соседей в обоих случаях равны 2, 3 и 3. Но соседи B и C вершины A соединены друг с другом: получается треугольник ABC. У D ни одна пара соседей A, E, F не соединена.
Для этой схемы используется отдельная таблица связей. После подсчёта степеней вершин и их соседей для A и D остались номера 1 и 4. Ниже выписаны соседи каждого номера и ячейки между этими соседями: звёздочка означает дорогу, прочерк её отсутствие. Для трёх соседей проверяются три пары.
| № | Соседи | Связи |
|---|---|---|
| 1 | 3, 4, 5 | 3-4: - 3-5: - 4-5: - |
| 4 | 1, 2, 6 | 1-2: - 1-6: - 2-6: * |
У номера 1 дорог между соседями нет, как у D. У номера 4 соседи 2 и 6 соединены, как B и C у вершины A. Поэтому A = 4, D = 1. Совпадение количества связей ещё не означает совпадения их устройства.
Проверка оставшихся вариантов
Тот же вывод можно получить, проверив предположение A = 1. Тогда вершины B и C должны получить два номера из 3, 4 и 5. Между любой парой этих номеров дороги нет, а ребро BC на схеме есть. Это противоречие исключает A = 1. Так же проверяются оставшиеся кандидаты, если сравнение признаков не дало единственного ответа.
Дополнительные сведения условия тоже ограничивают выбор. Например, если указано, что дорога AB длиннее AC, после сопоставления соответствующие числа в таблице должны удовлетворять этому условию.
Совпадение проверенных признаков ещё не доказывает симметрию: варианты могут различаться по другим связям.
Другой случай: в графе есть симметрия. Тогда отдельные буквы могут оставаться неразличимыми, хотя ответ уже определён. Например, если двум нужным пунктам подходят номера 2 и 5 в любом порядке, запись по возрастанию всё равно будет 25. Для ответа в порядке букв требуется различить эти два пункта. Подробности: соответствие и симметрия графов.
Полное переименование схемы полезно для проверки, но не всегда требуется для ответа. Достаточно обосновать нужные номера или показать, что все оставшиеся допустимые соответствия дают один результат.
Возможные ловушки
Ниже несколько ситуаций, в которых верное сопоставление или запись ответа могут нарушиться. Список не охватывает все возможные особенности условия.
- Сопоставление по алфавиту. Первая буква не обязательно соответствует номеру 1: обозначения выбраны независимо. Например, предположение A = 1 допустимо только как вариант для проверки. Оно должно сохранять количество дорог, соседей и все связи между ними.
- Оценка длины по рисунку. Более длинный отрезок на схеме не обязательно обозначает более длинную дорогу. Если масштаб не задан, рисунок сообщает о связях, а длина берётся из таблицы после определения номеров концов дороги. Сравнение длин, явно указанное в условии, при этом обязательно учитывается.
- Пропущенный пункт на линии. Если между A и C отмечен пункт B, нарисованы две дороги: AB и BC. Прямой дороги AC может не быть. Обратная ситуация — пересечение линий без обозначенного пункта: само по себе оно не создаёт новую вершину. При подсчёте дорог важны отмеченные пункты и концы линий.
- Лишняя дорога в сумме. Набор названных дорог может отличаться от маршрута между крайними пунктами. В задании EGE-01-0002 ↗ требуются GE и FH. На схеме они входят в цепочку H–F–E–G, но средняя дорога FE в вопросе не названа и в сумму не входит.
- Первое совпадение принято за доказательство. В задании EGE-01-0001 ↗ из В и Д выходят по четыре дороги. В таблице по четыре связи имеют сразу три номера: 2, 6 и 7. Одного подсчёта недостаточно: нужно сравнить соседей и проверить связи. Если несколько допустимых соответствий сохраняются, ответ должен быть одинаковым при каждом из них.
- Неверный порядок записи. Найти нужные номера и записать ответ — два отдельных шага. В задании EGE-01-0008 ↗ номера для B и C требуется расположить по возрастанию, без пробелов и знаков препинания. Запись в порядке букв здесь не требуется. В другой формулировке порядок может быть иным — его задаёт последнее предложение условия.