Ответ
52
Задание 1 ЕГЭ по информатике
Что проверяет: Графы и таблицы смежности
Задание 1 ЕГЭ по информатике проверяет тему «графы и таблицы смежности». Ниже вы найдёте 1 вариант с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.
Теория к заданию 1 ЕГЭ по информатике: графы и таблицы смежности
По схеме дорог и весовой таблице нужно сопоставить вершины графа со строками таблицы и найти длину указанных дорог.
Что нужно знать
- Степень вершины: число выходящих из неё рёбер; в таблице это количество заполненных ячеек в строке.
- Таблица симметрична относительно главной диагонали: вес ребра записан дважды.
- Сопоставление начинают с вершин, степень которых не повторяется: обычно это самые «бедные» и самые «богатые» вершины.
- Неповторяющиеся значения весов тоже помогают: если такое число встречается один раз, ребро определяется однозначно.
- После сопоставления каждой вершины полезно выписать соответствие между буквой и номером в отдельную табличку.
Как сопоставлять граф и таблицу
- Степень вершины: число выходящих из неё рёбер. В таблице это количество заполненных ячеек в строке.
- Начинайте с вершин, чья степень не повторяется: если только одна вершина имеет три ребра, её строка находится сразу.
- Затем используйте неповторяющиеся веса: если ребро длиной 7 в графе одно, в таблице оно тоже одно.
- Таблица симметрична относительно главной диагонали: вес из A в B равен весу из B в A.
- На главной диагонали всегда пусто, потому что вершина не соединена сама с собой.
- После сопоставления обязательно проверьте все рёбра, а не только те, по которым сопоставляли.
- Если спрашивают длину пути, складывайте веса рёбер вдоль маршрута, а не число рёбер.
Как решать задание 1
- Посчитайте степень каждой вершины на схеме и каждой строки в таблице.
- Сопоставьте вершины, степени которых не повторяются.
- Для оставшихся используйте связи с уже определёнными вершинами.
- Найдите в таблице веса нужных рёбер и сложите их.
- Запишите целое число.
Разбор примера
Общая схема: дана схема дорог с семью населёнными пунктами и таблица расстояний, где названия заменены буквами. Нужно найти длину дороги между двумя конкретными пунктами.
- Считаем степень каждой вершины на схеме и записываем рядом с ней число.
- Считаем количество заполненных ячеек в каждой строке таблицы.
- Находим вершину и строку с неповторяющейся степенью: это первая надёжная привязка.
- От неё идём к соседям: смотрим, какие веса стоят в её строке, и ищем те же числа на схеме.
- Заполняем соответствие до конца и проверяем каждое ребро на совпадение.
- Находим в таблице ячейку на пересечении нужных букв и записываем её значение.
Ответзначение из таблицы после полного сопоставления
Частые ошибки
- Считают степень вершины по рисунку неверно, пропуская ребро.
- Складывают не те рёбра, перепутав буквы и номера.
Задание 1 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.