Задание 1 ЕГЭ: как сопоставить граф и таблицу дорог
Граф и таблица в задании 1 ЕГЭ: степени вершин, связи с соседями, пошаговая схема и короткая проверка Python. Учебная задача и самопроверка.
Сразу к самопроверке
Автор материалаНикита Саралашвили
Обновлено Что требуется в задаче
Одна дорожная сеть показана двумя способами. На графе пункты обозначены буквами, а в таблице — числами в другом порядке. Числа внутри таблицы — длины прямых дорог; прочерк означает, что такой дороги нет.
Авторская разминка: дороги AB, AC, BC образуют треугольник; из C идёт дорога в D, из D — в E. Найдите длину прямой дороги C–D по графу и таблице ниже. Это не задача на кратчайший маршрут: складывать длины разных дорог не нужно.
Один граф — две системы обозначений
Найдите длину дороги C–D. Буквы на схеме и номера в таблице обозначают те же пункты. Прочерк означает отсутствие прямой дороги.
| Пункт | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | — | — | 4 | 7 | — |
| 2 | — | — | — | 8 | 6 |
| 3 | 4 | — | — | — | — |
| 4 | 7 | 8 | — | — | 5 |
| 5 | — | 6 | — | 5 | — |
A: 2, B: 2, C: 3, D: 2, E: 1. Не нужно угадывать по расположению рисунка.
Все соответствия для ответа
E = 3: одна дорога. C = 4: три дороги. D = 1: сосед E. В строке 1, столбце 4 стоит 7 — это дорога C–D. A и B можно поменять местами; на ответ это не влияет.
Шаг 1. Найдите особенные вершины
Степень вершины — число выходящих из неё дорог. У C три дороги, у E одна, у A, B и D по две. В таблице считайте заполненные клетки каждой строки, не складывая их значения.
У строки 4 три заполненные клетки, поэтому C = 4. У строки 3 одна клетка, поэтому E = 3. Мы нашли два надёжных ориентира.
Шаг 2. Сравните соседей
Одной степени недостаточно: у A, B и D она равна 2. Но только D соединена с E. В строке 3 единственная дорога ведёт к пункту 1. Значит, D = 1.
Теперь C–D соответствует 4–1. На их пересечении стоит 7. Симметричная клетка 1–4 даёт то же значение. Ответ: 7.
В этой разминке A и B взаимозаменяемы: два сопоставления сохраняют все дороги. Это допустимо, потому что в обоих вариантах запрошенная длина одинакова. В более сложном задании проверяйте, однозначно ли определяется именно то, что спрашивают.
Короткая проверка на Python
В строке tab каждый элемент перечисляет соседей соответствующего номера: у пункта 1 соседи 3 и 4; у пункта 2 — 4 и 5. В pic каждая пара — дорога на графе. var показывает буквы в порядке номеров 1…5.
from itertools import permutations
tab = '34 45 1 125 24'.split()
pic = 'AB AC BC CD DE'.split()
for var in permutations('ABCDE'):
if all(str(var.index(x) + 1) in tab[var.index(y)]
for x, y in pic):
print('C:', var.index('C') + 1, 'D:', var.index('D') + 1)
permutations перебирает порядки букв. var.index(x) + 1 находит номер пункта x. all требует, чтобы каждая дорога графа присутствовала в таблице. Программа дважды напечатает C: 4 D: 1: варианты отличаются только A и B. После этого читаем длину в таблице — 7.
Граница применимости: короткая запись соседей строкой подходит для однозначных номеров 1…9. При 10 и более используйте множества целых чисел. Проверять только наличие дорог достаточно здесь, потому что в обеих схемах пять дорог; при разном числе дорог нужно сравнивать также отсутствие связей.
Как проверять себя в новом условии
- Пересчитайте дороги у всех вершин.
- Начните с уникальной степени или связи с уже найденной вершиной.
- Проверяйте найденное соответствие по всем дорогам.
- Уточните, нужен номер пункта, длина дороги или сумма.
- Запишите ответ в требуемом формате.
Чтобы рассуждать от руки, откройте онлайн-черновик. Для полного обучения — курс по заданию 1. О переборе: документация Python.
Проверьте себя
Сначала решите самостоятельно. Затем проверьте ответ или откройте объяснение.
Ответ и объяснение
3. У E одна дорога; в строке 3 одна заполненная клетка.
Ответ и объяснение
4. D = 1, E = 3. Клетка 1–3 содержит 4.
Ответ и объяснение
11. 7 + 4 = 11. Здесь условие прямо просит сумму двух дорог.