Базовый (1 балл)
Время: 3-5 мин
Степени вершин
Таблица смежности
Вершины-маяки
Анализ окружения
Все задачи №{ topic_num } в каталоге
Задание №1. Анализ информационных моделей (Графы и таблицы)
Тема: Сопоставление весовой матрицы и графа дорог по степеням вершин и маякам
Цель задания — однозначно сопоставить буквенные вершины графа с номерами пунктов (П1–П7) в весовой матрице расстояний и найти длину конкретного ребра или сумму длин маршрутов. Выполняется строго вручную за 3 минуты методом анализа степеней и соседей-маяков.
1. Теоретический фундамент: Степени вершин графа
Степень вершины (валентность) — это количество рёбер (дорог), выходящих из данной вершины.
- В таблице смежности степень пункта $П_i$ равна количеству чисел (заполненных ячеек) в строке (или столбце) $П_i$.
- На чертеже степень вершины — это количество отрезков дорог, примыкающих к букве.
- Лемма о рукопожатиях: сумма степеней всех вершин графа всегда четна и равна удвоенному количеству ребер: $\sum \deg(v) = 2 \cdot |E|$.
2. Пошаговый 4-шаговый алгоритм решения («Метод Маяков»):
- Шаг 1. Таблица степеней:
Выпишите степени всех букв с рисунка: например, $A(2), B(3), C(4), D(3), E(2), F(3), G(4)$.
Посчитайте степени всех строк матрицы: например, $П1(3), П2(2), П3(4), П4(3), П5(2), П6(3), П7(4)$. - Шаг 2. Поиск уникальных маяков:
Найдите вершины, степень которых встречается единственный раз. Например, если степень 4 имеют только $C$ и $G$, а степень 2 имеют $A$ и $E$. - Шаг 3. Анализ набора соседей (Окружение):
Если две вершины имеют одинаковую степень (например, обе степени 3), посмотрите на степени их соседей:
• Вершина $B(3)$ соединена с вершинами со степенями{2, 3, 4}.
• Вершина $D(3)$ соединена с вершинами со степенями{4, 4, 3}.
По набору степеней соседей любая вершина определяется со 100% однозначностью! - Шаг 4. Извлечение ответа из матрицы:
Найдите пересечение нужной строки и столбца (например, строка $П3$ и столбец $П5$) и выпишите число на их пересечении.
3. Подробный разбор реальной экзаменационной задачи:
Условие: На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в км). Определите длину дороги из пункта Б в пункт Е.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | Степень | |
| П1 | 15 | 9 | 12 | 3 | ||||
| П2 | 24 | 18 | 2 | |||||
| П3 | 15 | 8 | 14 | 3 | ||||
| П4 | 8 | 11 | 2 | |||||
| П5 | 24 | 11 | 17 | 3 | ||||
| П6 | 9 | 17 | 20 | 3 | ||||
| П7 | 12 | 18 | 14 | 20 | 4 |
Решение:
- Единственная вершина степени 4 — это П7 (степень 4). На графе 4 дороги имеет только пункт В $\implies$ В = П7.
- Вершины степени 2 — это П2 и П4. На графе степень 2 имеют пункты А и Г. При этом пункт $А$ соединен с $В (П7)$, а пункт $Г$ соединен с пунктом $Д (П5)$.
- Смотрим на строку $П2$: она соединена с $П7 (В)$ и $П5$. Значит, А = П2, а Г = П4!
- Сосед $П2$ (кроме $П7$) — это $П5$, значит $Д = П5$.
- Смотрим, с кем соединен $П4 (Г)$: с $П3$ и $П5$. Значит, $Е = П3$.
- Оставшийся сосед $П7$ — пункт Б = П1.
- Нас просили найти длину дороги между Б (П1) и Е (П3): смотрим пересечение строки $П1$ и столбца $П3$ $\implies$ 15.
Ответ: 15
Разновидности и прототипы задания на экзамене
Тип 1: Граф с уникальными степенями вершин
Каждая вершина (или большинство) имеет уникальное число дорог (например, 2, 3, 4, 5) — сопоставляется напрямую за 1 минуту.
Тип 2: Граф с зеркальной осевой симметрией
Граф имеет две симметричные ветки (например, вершины A и B имеют одинаковое окружение). Длина искомой дороги инвариантна (одинакова) при любом выборе раскладки.
Тип 3: Поиск суммы длин нескольких ребер / составного пути
Требуется найти сумму протяженностей дорог между несколькими парами пунктов (например, из А в В и из C в F).
Анти-примеры (Типичные ошибки vs Как делать правильно)
Как делать НЕ надо:
Ошибка: Пытаться угадать соответствие на глаз без выписывания степеней
При схожем расположении вершин визуальное сопоставление приводит к ошибке в 60% случаев.Как делать ПРАВИЛЬНО:
Правильно: Сначала подписать степени всех вершин на рисунке и посчитать непустые ячейки в матрице!Как делать НЕ надо:
Ошибка: Забыть перепроверить вопрос в конце задачи
Найти длину дороги из А в Б вместо суммы длин дорог из А в Б и из Д в Е.Как делать ПРАВИЛЬНО:
Правильно: Всегда перечитывать последнее предложение условия перед окончательной записью ответа.Как делать НЕ надо:
Ошибка: Паниковать при симметричном графе
Думать, что решение неверно, если вершины А и К невозможно различить между собой.Как делать ПРАВИЛЬНО:
Правильно: При симметрии длина искомого ребра гарантированно одинакова для обоих вариантов сопоставления!
ГРОБ
ГРОБ №1: Полная круговая симметрия (все вершины степени 3)
Граф в виде правильной трехмерной призмы или куба, где абсолютно все 8 вершин имеют одинаковую степень 3.
Как обойти ловушку: В таких задачах сопоставление букв не единственно, но длина искомого ребра строго инвариантна (одинакова) при любом повороте. Выбирайте произвольную вершину за П1 и последовательно раскручивайте цепочку соседей.
Лайфхаки и подводные камни на экзамене:
- Таблица расстояний всегда строго симметрична относительно главной диагонали — анализируйте только верхний треугольник таблицы!
- Если вершина соединена со всеми остальными (вершина-звезда) — это строка с максимальным числом чисел в таблице.
- Для проверки решения посчитайте сумму степеней графа: она обязана в точности совпасть с удвоенным числом дорог.
- Если сомневаетесь между двумя вершинами одинаковой степени, выпишите степени их соседей в порядке возрастания: например, {2, 3, 4} vs {3, 3, 4}.