Базовый уровень · 1 первичный балл

Задание 1. Таблица ↔ граф

Учимся восстанавливать соответствие между буквенными вершинами графа и строками таблицы дорог. Главное — смотреть не на рисунок, а на структуру связей.

Начать урок Сразу к тренажёру

⏱ 20–30 минут◆ Графы▦ Таблицы✓ Автопроверка

Что нужно понять перед решением

В графе вершины — это объекты, а рёбра — связи между ними. В таблице та же самая структура записана строками и столбцами. Буквы и номера могут быть переставлены как угодно.

●

Вершина

Населённый пункт или другой объект на схеме.

—

Ребро

Прямая связь между двумя вершинами.

Степень

Количество рёбер, выходящих из вершины.

Ключевая идея

Если вершина на графе соединена с тремя соседями, ей может соответствовать только строка таблицы, где есть ровно три заполненные связи. Длины рёбер для первого сопоставления обычно не важны.

Два типа задания №1

Однозначное

Соответствие восстанавливается полностью

У графа достаточно отличительных признаков. Последовательно сопоставляем вершины и получаем единственный вариант.

Неоднозначное

Часть вершин может меняться местами

Полное соответствие не всегда нужно. Достаточно доказать, что искомая длина одинакова во всех допустимых вариантах.

Надёжный алгоритм решения

Посчитай степени вершин

Для каждой буквы на графе выпиши число соседей. Начинай с редких значений: степень 1, самая большая степень и т. п.

Посчитай заполненные связи в таблице

В каждой строке посчитай непустые ячейки вне главной диагонали. Это степень соответствующей вершины.

Закрепи уникальные пары

Если только одна вершина имеет степень 1 и только одна строка содержит одну связь — они соответствуют друг другу.

Сравни соседей уже найденных вершин

После первой пары задача резко упрощается. Смотри, с какими строками связана найденная строка, и сопоставляй её соседей.

Только потом бери длину дороги

Когда нужные буквы переведены в P1, P2, …, найди соответствующую ячейку таблицы.

Не делай так: не пытайся угадывать соответствие по положению вершины слева/справа/сверху. Компоновка графа не кодирует номера таблицы.

Пошаговый разбор собственного примера

Ниже граф и таблица описывают одну и ту же сеть дорог. Нумерация P1–P7 никак не связана с буквами A–G.

ГрафБуквенные вершины

Таблица дорогПусто = дороги нет

	P1	P2	P3	P4	P5	P6	P7
P1	—	7	12		9
P2	7	—		8			11
P3	12		—		6		13
P4		8		—		14
P5	9		6		—
P6				14		—
P7		11	13				—

ЗадачаОпредели длину дороги D–G

На графе степень 1 имеет только F. В таблице единственная строка с одной связью — P6. Значит, F = P6.

F соединена только с A. P6 соединена только с P4. Значит, A = P4.

A соединена с B и F. P4 соединена с P2 и P6. P6 уже занята вершиной F, следовательно B = P2.

Из структуры соседей получаем: C = P7, G = P3, E = P1, D = P5.

D–G соответствует P5–P3. В таблице на пересечении P5 и P3 стоит 6. Ответ: 6.

Тренажёр: восстанови соответствие

Используй тот же граф и таблицу, но теперь собери соответствие самостоятельно. Можно проверять сколько угодно раз.

Практика

Какая строка таблицы соответствует каждой вершине?

0 / 7

Финальный вопрос

Чему равна длина дороги D–G?

Шпаргалка на экзамен

Степени: посчитай соседей каждой вершины и заполненные связи каждой строки.
Уникальные признаки: начни с степени 1, максимальной степени и необычных комбинаций соседей.
Цепочка: после первой пары переходи к её соседям.
Не угадывай по рисунку: положение вершин ничего не говорит о P1, P2, …
Ответ: длину считывай только после того, как определил строки нужных букв.

Дальше

Задание 2. Таблицы истинности

Логические выражения и строки с пропущенными значениями.

← Каталог Задание 2 →