В статье рассматривается решение задания из ЕГЭ по информатике, связанной с анализом графов и матриц смежности для определения номеров населённых пунктов на схеме дорог. Описан как краткий алгоритм решения подобных задач, так и подробное решение конкретной задачи из открытого варианта ЕГЭ.
Задания №1 (по графам) из ЕГЭ по информатике проверяют навыки анализа и интерпретации информации, представленной в виде схем, таблиц или матриц смежности. Они могут включать:
- определение соответствия вершин и номеров в таблице;
- вычисление сумм длин дорог между пунктами;
- нахождение количества рёбер, степени вершины, маршрутов или других свойств графа.
Основные понятия, необходимые для решения:
- Схема (граф) – вершины обозначают пункты, рёбра — дороги между ними.
- Таблица (матрица смежности) – N × N таблица, где ячейка показывает наличие дороги или её длину.
Универсальный алгоритм решения задания
Подход к решению подобных задач можно разделить на несколько шагов:
1. Анализ графа:
- Определите степень каждой вершины – количество соединений с другими пунктами.
- Если указаны длины дорог, запишите их отдельно для каждой пары вершин.
- Найдите уникальные вершины или дороги – они помогут быстрее сопоставить схему и таблицу.
2. Сопоставление данных схемы и таблицы:
- Сравните связи между вершинами на схеме и данные в таблице смежности.
- Для вершин, соединённых с известными пунктами, определите недостающие свойства (номера вершин в таблице, протяжённость дорог, количество соединений или маршрутов).
3. Вычисление нужных величин:
- Если требуется сумма протяжённостей, сложите длины нужных рёбер.
- Если нужно подсчитать маршруты, соединения или степени вершин, отметьте все учтённые рёбра, чтобы не ошибиться.
- Используйте таблицу смежности для проверки правильности вычислений.
4. Запись ответа. Записывайте результат в формате, указанном в условии:
- целое число (например, сумма длин дорог);
- набор чисел в порядке возрастания (например, номера вершин);
- иные форматы, если это указано в задаче.
Советы:
- Начинайте с уникальных вершин или рёбер, чтобы быстрее определить сопоставления.
- Всегда перепроверяйте данные на схеме и в таблице, чтобы не допустить ошибок.
- Для задач с длинными путями или суммами используйте пометки или таблицу, чтобы не пропустить ни одного ребра.
- Этот алгоритм универсален: подходит для всех заданий по графам на ЕГЭ, включая сопоставление вершин, вычисление сумм длин дорог и подсчёт соединений.
Задание:
Алгоритм решения. Решение задач такого типа выполняется последовательными шагами, где номера пунктов определяются на основе количества соединений (степени вершины) и их взаимосвязей.
1. Определение уникальных вершин по числу рёбер.
Сначала внимательно рассмотрим схему и подсчитаем количество соединений для каждой вершины. Вершины с уникальным числом рёбер позволяют однозначно сопоставить их с номерами в таблице.
G соединяется с 3-мя вершинами (E соединяется с 2-мя вершинами, A – с 3-мя вершинами, C – с 3-мя вершинами). Можно записать количество вершин в скобках (2, 3, 3)
E соединяется с 2-мя вершинами (G соединяется с 3-мя вершинами, F – с 2-мя вершинами). Можно записать количество вершин в скобках (3, 2)
F соединяется с 2-мя вершинами (E соединяется с 2-мя вершинами, H – с 3-мя вершинами). Можно записать количество вершин в скобках (2, 3)
H соединяется с 3-мя вершинами (D соединяется с 2-мя вершинами, F – с 2-мя вершинами, B – с 2-мя вершинами). Можно записать количество вершин в скобках (2, 2, 2)
2. Сопоставление графа и таблицы.
Теперь будем рассматривать столбцы таблицы, сопоставлять с графом и искать соответствие номеров в таблице и букв в графе.
Так как вершина H («тройная» вершина) и имеет комбинацию (2, 2, 2), значит будем искать по вертикали столбец с тремя числами. Это столбцы 1, 5, 6 и 8. Так как нам нужна комбинация (2, 2, 2), смотрим по горизонтали строки, чтобы в данных столбцах было по 2 числа. Если смотреть на первый столбец, то мы увидим, что там, где число 15 (2 строка) 2 числа, где число 24 (5 строка) 3 числа, где число 12 (8 строка) 3 числа. А нам нужно, чтобы во всех строках было по 2 числа. Значит, 1 столбец – это не вершина H. 5-й и 8-й столбцы тоже не подходят. А 6-й столбик подходит, т.к. строки с числами 43, 9 и 37 имеют по 2 числа.
Вывод: H – номер 6.
Теперь, по ходу действия мы можем определить вершину F. Эта вершина «двойная», т.е. соединяется с 2-мя вершинами и имеет комбинацию (2, 3). Так как вершина F соединяется с H, рассматриваем строки 3, 4 и 7. В 3-й строке число 18 по вертикали находится в столбце с 3-мя числами, а нам нужно 2 числа в столбце. В 4-й строке число 41 тоже в столбце с 3-мя числами, значит она не подходит. А в 7 строке число 13 находится в столбце с 2-мя числами.
Вывод: F – номер 7.
Теперь, по ходу действия мы легко найдём вершину E. Так как она «двойная» и соединяется с вершиной F (это номер 7), мы видим, что число 13 находится во 2-м столбце.
Вывод: E – номер 2.
Теперь легко определить вершину G. Она соединяется с вершиной E. В этом столбце число 15 находится в строке с 3-мя числами. Это строка 1.
Вывод: G – номер 1.
3. Определение чисел по таблице.
Отвечаем на вопрос: расстояние от пункта G до E = 15 (смотрим пересечение в таблице номеров 1 и 2), от F до H = 37 (пересечение номеров 6 и 7). Сумма равна 52.
Ответ: 52