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

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

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

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

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

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

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

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

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

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

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

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

 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Г?

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

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

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

- Граф может содержать большее количество вершин (до 10–12), что делает ручной перебор каждого маршрута трудоёмким и подталкивает к использованию метода динамического подсчёта.

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

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

1. Ориентированный граф — это граф, рёбрам которого присвоено направление. На схеме направление указывается стрелкой. Двигаться можно только по стрелкам, против стрелки движения нет.

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

3. Динамический подход к подсчёту путей. Ключевая идея: количество способов попасть в некоторую вершину равно сумме количеств способов попасть во все вершины, из которых ведут стрелки в данную вершину. Иными словами, если в вершину X ведут стрелки из вершин A, B и C, то количество путей от старта до X равно сумме количеств путей от старта до A, от старта до B и от старта до C.

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

Пошаговый алгоритм решения (метод динамического подсчёта)

Рассмотрим классический пример. Дан ориентированный граф со следующими связями:

Требуется найти количество путей из А в К.

Шаг 1. Определить стартовую вершину и присвоить ей начальное значение.

Стартовая вершина — А. Количество способов оказаться в ней изначально равно 1 (мы уже здесь). Записываем на черновике: А = 1.

Шаг 2. Последовательно, двигаясь по стрелкам, вычислить количество путей для каждой следующей вершины.

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

- Вершина Б: в неё ведёт стрелка только из А. Следовательно, Б = А = 1.

- Вершина В: в неё ведёт стрелка только из А. Следовательно, В = А = 1.

- Вершина Г: в неё ведут стрелки из Б и В. Следовательно, Г = Б + В = 1 + 1 = 2.

- Вершина Д: стрелка только из Б. Д = Б = 1.

- Вершина Е: стрелка только из В. Е = В = 1.

- Вершина Ж: стрелки из Г и Д. Ж = Г + Д = 2 + 1 = 3.

- Вершина З: стрелки из Г и Е. З = Г + Е = 2 + 1 = 3.

- Вершина И: стрелки из Ж и З. И = Ж + З = 3 + 3 = 6.

- Вершина К: стрелки из И. К = И = 6.

Шаг 3. Записать ответ.

Ответ: 6.

Разбор модификации с дополнительным условием (прохождение через вершину)

Условие: Сколько существует различных путей из А в К, проходящих через город Г?

Шаг 1. Разбить задачу на два этапа.

Путь из А в К через Г обязательно состоит из двух частей: от А до Г и от Г до К. Поскольку все стрелки направлены «вперёд» и циклов нет, эти две части независимы.

Шаг 2. Вычислить количество путей от А до Г.

Используем тот же метод. А = 1.

Б = А = 1.

В = А = 1.

Г = Б + В = 1 + 1 = 2.

Итак, от А до Г ведут 2 пути.

Шаг 3. Вычислить количество путей от Г до К.

Теперь стартовой вершиной условно считаем Г. Присваиваем Г = 1 (мы уже здесь).

Ж = Г = 1.

З = Г = 1.

И = Ж + З = 1 + 1 = 2.

К = И = 2.

Итак, от Г до К ведут 2 пути.

Шаг 4. Перемножить результаты.

Каждый из двух путей от А до Г может быть продолжен каждым из двух путей от Г до К. Общее количество: 2 × 2 = 4.

Шаг 5. Записать ответ.

Ответ: 4.

Альтернативный метод (с вычитанием, если условие «не проходящих через»)

Если бы требовалось найти количество путей, НЕ проходящих через Г, можно было бы из общего количества путей (6) вычесть количество путей, проходящих через Г (4). Ответ: 6 – 4 = 2.

Разбор модификации с большим количеством вершин

В случае, когда граф содержит 10–12 вершин, ручной перебор становится слишком трудоёмким и чреват ошибками. Динамический метод остаётся тем же, но требует предельной аккуратности при определении порядка вершин. Полезно предварительно выписать все вершины в столбик и для каждой составить список входящих стрелок, а затем вычислять значения сверху вниз.

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

Задание оценивается в 1 первичный балл. Ответ — одно целое число. Балл выставляется при полном совпадении ответа с эталоном. Любое отклонение, включая ответ с избыточным количеством путей (из-за учёта несуществующих маршрутов) или недостаточным (из-за пропуска), приводит к нулевой оценке.

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

1. Хаотичный перебор вместо системного подсчёта. Ученик пытается пальцем или карандашом пройти все маршруты, неизбежно пропуская некоторые из них или проходя дважды. Лекарство — строгий динамический метод, исключающий необходимость рисовать каждый путь.

2. Игнорирование направления стрелок. Двигаться можно только по направлению, указанному стрелкой. Попытка пройти против стрелки (или туда-обратно) — грубая ошибка. Перед началом вычислений полезно убедиться, что граф воспринимается именно как ориентированный.

3. Неверное определение порядка вычисления. Если для вершины Г значение вычисляется раньше, чем для её предшественников Б и В, то вместо суммы Б+В будет использовано неполное или нулевое значение. Порядок должен строго соответствовать движению от старта.

4. Сложение вместо умножения при дополнительном условии. Если путь должен пройти через промежуточную вершину, количество путей от старта до неё и от неё до финиша не складываются, а перемножаются. Ошибка «сложил вместо умножения» крайне распространена.

5. Арифметические ошибки при суммировании. При большом количестве вершин (8–10) значения могут накапливаться до нескольких десятков. Ошибка в сложении на одном из этапов делает неверным весь последующий расчёт. Полезно проверять промежуточные суммы дважды.

6. Учёт несуществующих путей. Иногда ученик видит на рисунке перекрестье линий, не соединённое точкой (вершиной), и мысленно «прокладывает» там путь. Важно помнить: дорога существует только там, где есть явно обозначенная вершина и стрелка.

Заключение

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