Ответ
52
Задание 1 ЕГЭ по информатике
Что проверяет: Графы и таблицы смежности
Задание 1 ЕГЭ по информатике проверяет тему «графы и таблицы смежности». Ниже вы найдёте 4 варианта с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.
В таблице указана протяжённость дорог между населёнными пунктами (пустая клетка — прямой дороги нет). Определите длину кратчайшего пути из пункта A в пункт F, если передвигаться можно только по указанным дорогам.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 4 | 7 | ||||
| B | 4 | 2 | 9 | |||
| C | 7 | 2 | 3 | 8 | ||
| D | 9 | 3 | 2 | 6 | ||
| E | 8 | 2 | 3 | |||
| F | 6 | 3 |
Ответ
14
Перебираем маршруты по возрастанию длины. Прямой дороги A—F нет, поэтому идём через промежуточные пункты.
Выгоднее всего A—B (4), затем B—C (2), далее C—D (3), D—E (2) и E—F (3). Итого 4 + 2 + 3 + 2 + 3 = 14. Любой другой маршрут длиннее: например, A—C—D—F даёт 7 + 3 + 6 = 16. Ответ — 14.
В таблице указана протяжённость дорог между населёнными пунктами. Определите длину кратчайшего пути из пункта A в пункт F.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 3 | 10 | ||||
| B | 3 | 4 | 6 | |||
| C | 4 | 2 | 9 | |||
| D | 10 | 2 | 5 | |||
| E | 6 | 1 | ||||
| F | 9 | 5 | 1 |
Ответ
10
Из A выходят две дороги: в B (3) и в D (10). Короткое начало — через B.
Дальше из B дешевле всего попасть в E (6), а из E в F ведёт дорога длиной 1. Получаем 3 + 6 + 1 = 10. Маршрут A—B—C—D—F стоит 3 + 4 + 2 + 5 = 14, он длиннее. Ответ — 10.
В таблице указана протяжённость дорог между населёнными пунктами. Определите длину кратчайшего пути из пункта A в пункт F.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 5 | 2 | ||||
| B | 5 | 3 | 8 | |||
| C | 2 | 6 | 4 | |||
| D | 3 | 6 | 2 | |||
| E | 8 | 4 | 7 | |||
| F | 2 | 7 |
Ответ
10
Здесь два маршрута дают один и тот же результат. Через C: A—C (2), C—D (6), D—F (2) — всего 10. Через B: A—B (5), B—D (3), D—F (2) — тоже 10.
Маршрут через E дороже: A—C—E—F даёт 2 + 4 + 7 = 13. Ответ — 10.
Теория к заданию 1 ЕГЭ по информатике: графы и таблицы смежности
По схеме дорог и весовой таблице нужно сопоставить вершины графа со строками таблицы и найти длину указанных дорог.
Что нужно знать
- Степень вершины: число выходящих из неё рёбер; в таблице это количество заполненных ячеек в строке.
- Таблица симметрична относительно главной диагонали: вес ребра записан дважды.
- Сопоставление начинают с вершин, степень которых не повторяется: обычно это самые «бедные» и самые «богатые» вершины.
- Неповторяющиеся значения весов тоже помогают: если такое число встречается один раз, ребро определяется однозначно.
- После сопоставления каждой вершины полезно выписать соответствие между буквой и номером в отдельную табличку.
Как сопоставлять граф и таблицу
- Степень вершины: число выходящих из неё рёбер. В таблице это количество заполненных ячеек в строке.
- Начинайте с вершин, чья степень не повторяется: если только одна вершина имеет три ребра, её строка находится сразу.
- Затем используйте неповторяющиеся веса: если ребро длиной 7 в графе одно, в таблице оно тоже одно.
- Таблица симметрична относительно главной диагонали: вес из A в B равен весу из B в A.
- На главной диагонали всегда пусто, потому что вершина не соединена сама с собой.
- После сопоставления обязательно проверьте все рёбра, а не только те, по которым сопоставляли.
- Если спрашивают длину пути, складывайте веса рёбер вдоль маршрута, а не число рёбер.
Как решать задание 1
- Посчитайте степень каждой вершины на схеме и каждой строки в таблице.
- Сопоставьте вершины, степени которых не повторяются.
- Для оставшихся используйте связи с уже определёнными вершинами.
- Найдите в таблице веса нужных рёбер и сложите их.
- Запишите целое число.
Разбор примера
Общая схема: дана схема дорог с семью населёнными пунктами и таблица расстояний, где названия заменены буквами. Нужно найти длину дороги между двумя конкретными пунктами.
- Считаем степень каждой вершины на схеме и записываем рядом с ней число.
- Считаем количество заполненных ячеек в каждой строке таблицы.
- Находим вершину и строку с неповторяющейся степенью: это первая надёжная привязка.
- От неё идём к соседям: смотрим, какие веса стоят в её строке, и ищем те же числа на схеме.
- Заполняем соответствие до конца и проверяем каждое ребро на совпадение.
- Находим в таблице ячейку на пересечении нужных букв и записываем её значение.
Ответзначение из таблицы после полного сопоставления
Частые ошибки
- Считают степень вершины по рисунку неверно, пропуская ребро.
- Складывают не те рёбра, перепутав буквы и номера.
Задание 1 входит в ЕГЭ по информатике. Это единственная страница сайта, где собраны все варианты этого номера: текст условия, картинка задания, правильный ответ, разбор решения и теория с алгоритмом. Остальные номера открываются в списке выше, а их перечень с темами есть в списке заданий ЕГЭ по информатике.