ОГЭ по информатике: Графы — кратчайший путь по таблице расстояний (задание 4)

Задание 4 ОГЭ по информатике проверяет умение анализировать простейшую модель — граф дорог, заданный таблицей расстояний (весовой матрицей). В кодификаторе ОГЭ 2026 года это элемент 2.11: граф, вершина, ребро, путь, вес ребра, весовая матрица, длина пути, поиск оптимального пути. Задание базового уровня и приносит 1 балл, но ошибки в нём очень типичны: ученик выбирает прямую дорогу, не проверив обходные пути, пропускает маршрут через три-четыре промежуточных пункта или неверно читает таблицу.

Материал построен так, чтобы отработать все эти ловушки на оригинальных таблицах. В квизе — задачи на длину кратчайшего пути, где прямая дорога оказывается длиннее обхода; маршруты через четыре промежуточных пункта; дополнительные условия «путь должен проходить через пункт C» и «дорогу B–D закрыли на ремонт»; вопрос о «жадном» выборе, когда турист всякий раз едет по самой короткой дороге и проигрывает несколько километров. Отдельные вопросы учат читать весовую матрицу: сколько дорог записано в симметричной таблице, из какого пункта выходит больше всего дорог, какой список дорог соответствует таблице и почему таблица симметрична.

Каждое пояснение показывает полный перебор путей с суммами, поэтому по ним удобно проверить собственный ход решения. Карточки повторяют термины (граф, ребро, вес, весовая матрица, длина пути) и приёмы. Письменная работа требует записать решение целиком: построить матрицу по списку дорог, перебрать все пути, разбить задачу «через пункт D» на две части, привести собственный пример, на котором «жадный» способ ошибается. В режиме экзамена экзаменатор задаёт задачи по одной и просит объяснить выбор маршрута.

Материал подходит для 9 класса при подготовке к ОГЭ и для повторения темы «Графы» в курсе информатики. Все таблицы составлены специально для этого материала и не повторяют задания открытого банка.

Как работать с материалом: сначала пройти квиз и после каждой ошибки сравнить свой перебор с пояснением — чаще всего пропускается обходной путь через три-четыре пункта. Затем повторить карточки и выполнить письменную работу: её можно распечатать, решить от руки и отправить фотографии на проверку. Полезная привычка для экзамена — выписывать дороги из таблицы списком и перебирать пути деревом, не заходя повторно в посещённый пункт.

• Читать весовую матрицу графа: находить дороги, их длины и число дорог из пункта
• Находить длину кратчайшего пути систематическим перебором путей без повторных пунктов
• Решать задачи с условиями «через пункт» и «дорога закрыта»
• Объяснять, почему выбор самой короткой дороги на каждом шаге не гарантирует кратчайший путь

Кодификатор ОГЭ 2026 по информатике, элемент 2.11 (граф, вершина, ребро, путь; длина (вес) ребра; весовая матрица; длина пути; поиск оптимального пути). Спецификация: задание 4, базовый уровень, 1 балл.