В современной практике подготовки к ОГЭ по информатике особое место занимают задания на поиск перемещений в сетевых структурах. С развитием экзаменационных материалов такие вопросы прочно вошли в экзамен 2024–2026 гг. Зачастую упражнение на поиск связей оказывается в составе более сложного номера (например, на анализ планов) и приносит 1–2 первичных очка, которые могут повлиять на итоговую оценку. Поэтому уметь быстро и уверенно решать вопрос 15 на ОГЭ по информатике (планы дорог) крайне важно.
С точки зрения структуры, ОГЭ в 2026 отличается от более ранних версий: количество заданий увеличилось, и вопрос с алгоритмом «для исполнителя» стал двухчастным. Тем не менее упражнения на сетевые структуры встречаются в «теоретической» части (обычно в заданиях на анализ диаграмм и планов). Так, например, в демоверсии 2025/2026 по информатике можно увидеть номера, где «на рисунке представлена сеть дорог, связывающих города A, B, C...» с одной или несколькими дополнительными условиями. Требуется определить все возможные способы передвижения между заданными точками. Такое упражнение демонстрирует практически всю логическую структуру подобных вопросов: нужно определить начало и конец перемещения, учесть обязательные (через какие города идти) и запрещённые промежуточные узлы.
Отметим изменения последних лет: в 2025 году ФИПИ разделил прежнее задание №15 на две части (15.1 и 15.2), но упражнения на сетевые структуры остались в первых разделах работы. Максимальный первичный результат за работу по информатике увеличен, а заданий стало больше. Учитывая эти изменения, важно системно подготовиться именно к теме «сети и поиск перемещений», чтобы обеспечить себе 2 очка по этому типу вопроса.
В этой статье представлен полный гайд — подробный конструктор решения вопроса 15 (по сетевым структурам). Мы пошагово опишем методику разбора формулировки, моделирование ситуации в виде ориентированной или неориентированной сети и вычисление итогового значения (количество вариантов или кратчайшее расстояние). Будут приведены готовые фразы и чек-листы для каждого этапа. Также мы разберём реальные примеры из официальных сборников и выделим типовые ошибки, чтобы ученик мог избежать их на экзамене.
Теоретическая база
Граф — математический объект для описания соединений.
Направленная структура: каждая связь имеет ориентацию (как односторонняя дорога: из пункта A в B можно попасть, обратно — нет, если связь направлена). Такие ориентированные соединения иногда называют дугами. Ненаправленная структура — связи без ориентации (двусторонние). На экзамене чаще встречается первый вариант (например, на плане дорог указано направление движения).
Модель соединений: объекты (города, узлы) связаны линиями (дороги). Перемещение — последовательность связей между двумя объектами. Простое перемещение не использует повторяющихся связей; элементарное — ещё и не повторяет объекты (кроме замкнутой последовательности, где начало и конец совпадают). В ОГЭ обычно рассматривают перемещения без возврата в пройденные узлы. Замкнутая последовательность — это когда начало и конец одинаковы. Древовидная структура — связная модель без замкнутых участков, но на дорожных картах чаще встречаются произвольные ориентированные построения.
Алгоритмы обхода: «в ширину» (BFS) и «в глубину» (DFS) позволяют исследовать модель или найти нужное перемещение. BFS идёт по слоям (очередь), DFS углубляется по одной ветви (стек). Временная оценка — O(V+E), где V — количество узлов, E — количество связей. На экзамене чаще применяют ручной подсчёт вариантов, но понимание принципов помогает. Для связей с весами используют алгоритм Дейкстры, однако в ОГЭ веса малы и сравниваются вручную.
Критерии ОГЭ 2024–2026: задания типа «Диаграммы, планы, карты» проверяют умение анализировать схему. Вопрос может содержать несколько частей: число маршрутов с заданными свойствами, длина кратчайшего и т.д. За каждую часть начисляется балл. Ошибка в начальном/конечном узле приводит к потере баллов. Важно давать полное обоснование.
Метод подсчёта (рекомендуемый ФИПИ): записать количество маршрутов до каждого узла, начиная с начального. Для узла X это число равно сумме значений всех узлов, из которых есть прямая связь в X. Последовательный подсчёт по схеме (динамическое программирование) даёт верный ответ.
Итог: база включает понятие схемы, её видов (ориентированная/неориентированная), определение маршрута, простого/элементарного маршрута, алгоритмы обхода и метод суммирования. Ученик должен знать критерии ФИПИ и уметь применять их при ручном подсчёте или обосновании отсутствия маршрута.
Рисунок: пример ориентированного графа (все рёбра имеют направление). Здесь вершины 1–4 связаны направленными рёбрами. В подобных схемах условие «двигаться можно только по стрелке» соответствует именно ориентированному графу.
Пошаговый алгоритм решения
Мы разработаем подробный конструктор решения, который поможет не пропустить ни одного этапа. Алгоритм можно разбить на пять основных шагов:
Анализ задачи (понимание условий).
Анализ условия
- Определите, есть ли на схеме направления (если сказано «только в одну сторону» — структура ориентированная).
- Чётко укажите начальный и конечный пункты (например, A → I).
- Выпишите обязательные и запретные промежуточные объекты (например, «обязательно через B», «не через Г»).
- Проверьте полноту данных: число пунктов, описание связей (обычно на рисунке) и веса (длины, время), если они есть.
Построение схемы
- Восстановите по условию все связи между пунктами (направленные или нет).
- Отметьте обязательные и исключённые объекты (запретные — не рассматривайте, обязательные — подчеркните).
- Убедитесь, что от начального к конечному есть связность (иначе ответ — «нет»).
Выбор метода
- Для подсчёта числа вариантов используйте правило: количество способов добраться до пункта X равно сумме способов для всех пунктов, из которых есть прямая связь в X. Запретные пункты не участвуют, обязательные учитываются только через них.
- Для нахождения кратчайшего расстояния (с весами) применяйте ручной аналог алгоритма: начальному пункту присвойте 0, остальным — бесконечность, затем последовательно обновляйте расстояния через соседние пункты, выбирая минимум.
Вычисления
- Для подсчёта вариантов: в начальном пункте запишите 1 (единственный способ «остаться на месте»). Обходите пункты в порядке удаления от старта (по направлению связей). Для каждого X вычисляйте сумму по входящим связям, с учётом ограничений. В ответе — число для конечного пункта.
- Для кратчайшего расстояния: фиксируйте минимальные значения, итеративно пересчитывая через новые пункты. Итог — минимальная сумма весов до конечного.
Проверка
- Сравните ответ с условиями: все ограничения (обязательные/запретные) учтены.
- При сомнениях пересчитайте разбивкой на этапы (например, A→B и B→I, перемножив варианты).
- Оформите результат чётко (число или значение расстояния). Каждый шаг обоснуйте кратко — это требуется по критериям оценивания.
Укрепим алгоритм примерами шаблонных фраз:
«Если путь должен проходить через город B, то при подсчёте для городов после B считаем только пути, идущие через B. Если же запрещено через G, то при суммировании не используем P(G).»
«В итоге получили P(I)=12, значит ответ — 12 различных путей из A в I (с учётом заданных ограничений).»
Этот алгоритм похож на «шпаргалку по информатике», позволяющую шаг за шагом прийти к решению без упущений.
Частые ошибки и советы
Типичные ошибки при решении таких графовых задач связаны с невнимательностью к условиям и неправильной моделью:
Пропуск вершины (запрещённой). Часто учащиеся по невнимательности продолжают учитывать пути через запрещённый город. Например, сказано «не через G», а в таблице всё равно суммируют пути, ведущие через G. Правило: при подсчёте просто не учитывайте P(G).
Неправильная иерархия расчётов. Порядок подсчёта должен «соответствовать топологическому порядку» графа: от исходной вершины по направлению стрелок. Иногда считают не в том порядке, пропуская вершину, что приводит к ошибке в суммах. Решение: выпишите вершины слоями или в порядке усложнения.
Повторный учёт одного и того же пути. Если в графе есть параллельные пути (через разные ветки), важно считать их все, но не считать один и тот же путь дважды. Проверяйте, не даёт ли формула двойного сложения.
Счёт «кратчайшего пути» вместо «числа путей». Ошибочно путая две разные задачи (количество путей и кратчайший путь), ученики иногда совершают лишние действия. Нужно внимательно прочитать: в одном варианте спрашивают количество маршрутов, в другом — минимальную длину. Правильно: если просят число, вычислять суммированием (динамикой); если длину, строить таблицу расстояний (или использовать Дейкстру).
Формулировки ответов. Ошибкой считается не оформить ответ как «числовую величину». Всегда пишите конкретно: «Всего существует 12 путей» или «Минимальная длина = 17».
Совет по проверке: пройдитесь по ключевым вершинам и проверьте вручную 1–2 пути. Если условие «через B» и «не через G», можно мысленно представить: исключили G, все маршруты идут через B. Должно совпасть с вашим числом. При необходимости разделите задачу на простейшие: сначала найдите пути до B, потом от B до конца, и умножьте.
Другой приём — «обратное решение». Пусть вам дали ответ N. Попробуйте сверить: если в A поставить 1 и перестроить расчёт, действительно ли получается N. Если нет — где был пропуск.
Практика: тренировочные задания
Задача 1: Ориентированный граф со схемой дорог. Найдите число путей из А в Е, проходящих через В, но не через D. (Подсказка: аналогично основному примеру, исключить D из подсчёта.)
Ответ: 10 (использовать метод динамического подсчёта, P(E)=P(A)+P(B)+… с учётом условий).
Задача 2: Найти все пути из C в F в графе, где веса дорог [C→E]=2, [E→F]=3, [C→F]=6. (Подсказка: ищем кратчайший путь.)
Ответ: Кратчайший путь — C→E→F с суммарным весом 5 (метод Дейкстры).
Задача 3: На графе подсчитать число путей из M в N без дополнительных условий. (Детали: пример с 4 вершинами.)
Ответ: Самостоятельно подсчитать таблицей (для примера получается 7).
Задача 4: Город A соединён с B и C, B соединён с D, C — с D и E. Сколько путей из A в D без условия? (Простой граф)
Ответ: 3 (A→B→D, A→C→D, A→B→A→B→D не считается — пути простые).
Задача 5: Найдите число маршрутов из P в Q, проходящих через R, если P→R соединено, R→Q соединено, и есть дополнительные ветви, которыми нельзя пользоваться. (Ситуация: R — обязательная вершина.)
Ответ: где-то 2–4 (зависит от конкретного графа), использовать перемножение как вариант.
Интеграция в общую подготовку к ОГЭ
Умение решать задачи по графам должно стать частью ежедневной подготовки в июне. Вот рекомендации:
Регулярная практика. Начните с простых примеров (поиск путей без условий) и постепенно добавляйте ограничения (через/не через). Делайте 1–2 подобных задания в день.
Повторение: Не реже раза в неделю возвращайтесь к теме «графы», составляйте собственные небольшие графы и проверяйте себя. После основных тем (циклы, алгоритмы) интегрируйте графы в комплексные тесты.
Упражнения на скорость: Установите таймер (например, 3–5 минут на задачу). Это поможет потом не «завалиться на время» экзамена. В ОГЭ важно быстро считать простые пути и вписывать ответ.
Зачем это важно? Каждый первичный балл в информатике конвертируется в итоговую оценку. Средний по России балл для поступления в профильные 10-е классы лежит около 15 из 21. Относительно небольшое задание на 2 балла может увеличить ваш суммарный балл с, скажем, 13 до 15, что решает вопрос «проходного балла». Помните, что ОГЭ по информатике строится на сумме первичных баллов (и вторичной шкале), поэтому «полный балл» в таких графовых задачах напрямую повышает итог.
В таблице ниже пример расчёта для понимающих связь первичные–вторичные баллы:
Первичные баллы за информатику (сумма)
- 10–11 баллов - «3» низкий проходной порог
- 12–14 баллов - «4» средний диапазон
- 15–21 баллов - «5» высокий диапазон (напр., 17+ для «5»)
Добавив 2 балла за задачу на графы, вы можете перейти в следующую категорию оценки.
Таким образом, полные баллы за задание на графы помогают повысить общий результат ОГЭ.
Заключение
Итоговый чек-лист перед экзаменом по графам:
- Внимательно прочитал условие: правильно выделены начало, конец, «через», «не через».
- Построил граф (ориентированный/неориентированный) и отметил обязательные/запрещённые вершины.
- Применил один из подходов: динамический подсчёт путей или алгоритм Дейкстры для кратчайшего пути.
- В подпунктах решения использовал шаблон «P(X)=Σ путей (предшественников)», исключил лишние вершины.
- Проверил, что конечный ответ соответствует формату (число/маршрут) и обозначил его.
- Повторил расчёт альтернативным способом (разделение на подпути или счёт вручную) для контроля.
Психологически настройтесь: этот номер — один из последних и непростых. Оставьте его на финал, но тренируйтесь заранее. Даже небольшой успех здесь приносит ощутимые очки. Используйте наши шаблоны и порядок действий — и логика станет понятной. Уверенность и чёткость — залог хорошего результата.
А если хотите отработать этот номер под руководством экспертов, обратитесь в школу «Матрица» — там помогут разобрать все сложные моменты.