Задание 4 ОГЭ по информатике: анализ графовых моделей и поиск кратчайшего пути
материал для подготовки к егэ (гиа) по информатике и икт (9 класс)

Задание 4 ОГЭ по информатике: анализ графовых моделей и поиск кратчайшего пути

Задание №4 в структуре экзаменационной работы относится к базовому уровню сложности и проверяет пространственное и логическое мышление выпускника. В отличие от заданий на программирование или формальную логику, здесь требуется умение «читать» графическую модель — взвешенный граф или табличную схему дорог — и находить оптимальный маршрут между заданными пунктами.

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

Что проверяет задание

Согласно спецификации контрольных измерительных материалов, задание №4 проверяет следующие предметные результаты:

- Умение читать и анализировать информационные модели, представленные в графической форме (взвешенные графы) и табличной форме (матрицы смежности или весовые таблицы).

- Понимание понятий: вершина графа, ребро, вес ребра, путь, длина пути, кратчайший путь.

- Способность находить кратчайший маршрут между двумя заданными вершинами, учитывая веса рёбер.

- Владение навыками систематического перебора вариантов для нахождения оптимального решения.

Принципиально важно: от ученика не требуется знание формальных алгоритмов Дейкстры или Флойда. Задания ОГЭ построены так, что графы невелики, и кратчайший путь может быть найден путём аккуратного, организованного перебора. Однако без чёткой методики и здесь легко запутаться.

Типовая формулировка задания

В открытом банке ФИПИ и демоверсиях задание формулируется следующим образом:

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице:

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Возможны модификации:

- Представление данных в виде взвешенного графа (схемы дорог с подписанными длинами), а не таблицы.

- Увеличение количества вершин до 7–8 (с соответствующим усложнением перебора).

- Требование найти кратчайший путь между пунктами, не соединёнными прямой дорогой (то есть путь обязательно будет состоять из нескольких рёбер).

- Введение дополнительных условий, например, обязательного прохождения через некоторый промежуточный пункт.

Неизменным остается суть: дана система связанных между собой объектов с указанными расстояниями, необходимо найти маршрут минимальной суммарной длины между двумя конкретными пунктами.

Фундаментальные понятия, которые необходимо актуализировать перед решением

1. Граф как модель. Вершины графа — это населённые пункты, перекрёстки, узлы сети. Рёбра — это дороги, соединяющие их. Вес ребра — длина дороги в заданных единицах (километрах).

2. Симметричность дорог. В задании ОГЭ все дороги считаются двусторонними, а их длина не зависит от направления движения. Поэтому таблица (матрица) всегда симметрична относительно главной диагонали, что можно использовать для проверки корректности её заполнения на черновике.

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

4. Петли и кратные рёбра. В заданиях ОГЭ петли (дороги из пункта в самого себя) и кратные рёбра (несколько разных дорог между одной и той же парой пунктов) не встречаются, что упрощает модель.

Пошаговый алгоритм решения

Рассмотрим универсальную последовательность действий на примере типовой задачи, приведённой выше.

Шаг 1. Визуализировать данные.

Если условие дано в виде таблицы, первым делом необходимо построить граф на черновике. Для этого рисуем шесть точек, обозначаем их буквами от A до F. Затем проходим по таблице: как только находим числовое значение на пересечении строки и столбца, соединяем соответствующие вершины ребром и подписываем его вес.

В нашем примере:

- A–B: 3

- A–D: 7

- B–C: 2

- B–E: 5

- C–D: 1

- C–F: 4

- D–E: 2

- E–F: 3

Шаг 2. Выписать начальный и конечный пункты.

Чётко фиксируем: начальный пункт — A, конечный — F. Все маршруты будем строить от A к F.

Шаг 3. Организовать перебор маршрутов по нарастающей длине.

Это ключевой методический момент. Нельзя хаотично перебирать все мыслимые пути — необходимо двигаться системно. Начинаем с самого короткого возможного маршрута, постепенно увеличивая количество промежуточных вершин.

Прямой дороги между A и F в таблице нет (клетка пуста), поэтому кратчайший путь будет состоять как минимум из двух рёбер.

Рассмотрим возможные маршруты:

Маршруты из трёх вершин (одна пересадка):

- A–B–F: нет прямой дороги B–F.

- A–D–F: нет прямой дороги D–F.

Таких маршрутов нет — переходим к маршрутам с двумя пересадками.

Маршруты из четырёх вершин (две пересадки):

Выпишем все возможные цепочки от A к F через две промежуточные вершины.

1. A–B–C–F: длина = AB(3) + BC(2) + CF(4) = 9.

2. A–B–E–F: длина = AB(3) + BE(5) + EF(3) = 11.

3. A–D–C–F: длина = AD(7) + DC(1) + CF(4) = 12.

4. A–D–E–F: длина = AD(7) + DE(2) + EF(3) = 12.

Маршруты из пяти вершин (три пересадки):

Проверим, не окажется ли какой-нибудь из этих путей короче уже найденных.

5. A–B–C–D–E–F: длина = 3+2+1+2+3 = 11 (не короче).

6. A–D–E–B–C–F: длина = 7+2+5+2+4 = 20 (заведомо больше).

И так далее — очевидно, что более длинные цепочки будут давать сумму, превышающую 9.

Шаг 4. Выбрать минимальное значение.

Среди всех найденных путей наименьшую длину имеет маршрут A–B–C–F: 9 километров.

Шаг 5. Проверить корректность.

Убедимся, что все рёбра маршрута A–B–C–F действительно существуют: A–B есть (3), B–C есть (2), C–F есть (4). Путь существует, его длина вычислена верно.

Шаг 6. Записать ответ в бланк.

Ответом является одно целое число — длина кратчайшего пути. Никаких дополнительных символов, буквенных обозначений вершин или единиц измерения (км) в бланк вносить не нужно.

Разбор модификаций условия

Модификация 1 (граф вместо таблицы).

Если в условии дан уже нарисованный граф, пропускаем шаг 1 и сразу переходим к перебору. Однако следует быть внимательным: иногда на схеме расстояния подписаны мелко, и их легко перепутать. Рекомендуется на черновике выписать все связи с весами в виде списка, аналогичного тому, что мы составили при разборе таблицы.

Модификация 2 (обязательное прохождение через промежуточный пункт).

В некоторых вариантах условие формулируется так: «Определите длину кратчайшего пути между A и F, проходящего через пункт C». В этом случае задача сводится к сумме двух кратчайших путей: от A до C и от C до F. Находим их независимо и складываем.

Модификация 3 (поиск пути с максимальным расстоянием при ограниченном числе пересадок).

Встречается реже, но требует того же системного перебора, только с выбором максимума, а не минимума.

Критерии оценивания и формат ответа

Задание оценивается в 1 первичный балл. Ответ — одно целое число. Балл выставляется при полном совпадении ответа с эталоном. Частично верный ответ, ответ с лишними символами, десятичной запятой или пробелами не засчитывается.

Типичные ошибки и стратегии их предотвращения

1. Пропуск короткого пути из-за несистемного перебора. Самая распространённая ошибка: ученик видит несколько очевидных маршрутов и выбирает самый короткий из них, не проверив все возможные варианты. В сложных графах неочевидный путь через несколько промежуточных вершин может оказаться короче прямого. Лекарство — строгий, методичный перебор, начиная с путей с наименьшим числом вершин.

2. Неверное чтение таблицы. Взяв значение из ячейки, ученик путает строки и столбцы, приписывая дороге неверную длину. Перед построением графа полезно проверить симметричность таблицы: если на пересечении A и B стоит 3, то на пересечении B и A должно стоять то же самое число. Если это не так — в условии опечатка или ученик неверно читает таблицу.

3. Арифметические ошибки при суммировании. В процессе перебора, особенно при просчете длинных цепочек, легко допустить ошибку сложения. Рекомендуется каждую сумму проверять дважды, а все промежуточные вычисления фиксировать на черновике в структурированном виде.

4. Невнимательность к единицам измерения. Иногда длина дорог указана в километрах, иногда — в условных единицах. Ответ всегда записывается как число без указания единиц, но спутать километры с метрами (если в задании указаны метры) невозможно, так как числа будут заведомо другого порядка. Однако сам факт такой невнимательности говорит о поверхностном чтении условия.

5. Добавление лишних символов в бланк ответов. Запись «9 км» или «9 километров» вместо «9» обнуляет правильно решённое задание. Формат ответа всегда одинаков: только число.

Пример решения с подробным комментарием

Условие: дана таблица расстояний между пунктами A, B, C, D, E. Найти кратчайший путь между A и E.

Таблица:

Решение:

1. Строим граф по таблице. Рёбра: A–B (4), A–C (8), B–D (3), B–E (7), C–D (2), D–E (1).

2. Прямой дороги A–E нет. Ищем маршруты с пересадками.

3. Маршруты из трёх вершин:

   - A–B–E: 4 + 7 = 11.

   - A–C–D–E: нет, это 4 вершины.

   Маршруты из четырёх вершин:

   - A–B–D–E: 4 + 3 + 1 = 8.

   - A–C–D–E: 8 + 2 + 1 = 11.

4. Минимальная длина: 8 (маршрут A–B–D–E).

5. Проверяем существование всех рёбер: A–B (есть, 4), B–D (есть, 3), D–E (есть, 1). Путь корректен.

Ответ: 8.

Заключение

Задание №4 ОГЭ по информатике — это тест на системность мышления и аккуратность. От ученика не требуется специальных алгоритмических знаний, но требуется выработанная привычка не доверять интуиции, а последовательно проверять все возможные варианты. Для успешного выполнения задания рекомендуется прорешать 15–20 прототипов из открытого банка ФИПИ, обращая внимание как на табличную, так и на графическую форму представления данных. При правильно организованной работе время выполнения не превышает 3–4 минут, а гарантированный балл становится надёжным вкладом в итоговый результат экзамена.