Продолжаем разбор задач ОГЭ.
Разберем задачу номер 4 из демо-варианта ОГЭ по информатике за 2026 год.
Условие задачи:
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Каждый пункт можно посетить только один раз.
Решение:
Задачи такого типа проще всего решить, нарисовав их графическую модель.
Обозначим на каждом пути длину маршрута, полученную из исходной таблицы;
АВ=2
АС=4
АЕ=6
ВС=1
СD=5
CE=1
DE=3
Теперь надо рассмотреть, какие существуют пути из А в D (без повторов городов), всего получаем 6 вариантов:
- ABCD
- ABCED
- ACD
- ACED
- AED
- AECD
Требуется найти сумму расстояний для каждого маршрута и выбрать из них наименьшее. Если сумма сразу получается достаточно большой (больше предыдущих), то можно для экономии времени на экзамене и не досчитывать маршрут до конца (как не оптимальный).
Итого получаем для каждого маршрута:
1. ABCD
ABCD = 2+1+5 = 8
2. ABCED
ABCED = 2+1+1+3 = 7 (меньше)
3. ACD
ACD = 4+5 = 9 (больше)
4. ACED
ACED = 4+1+3 = 8 (больше)
5. AED
AED = 6+3 = 9 (больше)
6. AECD
AECD = 6+1+5 = 12 (больше)
Выбираем самый короткий из маршрутов, это 7.
Ответ задачи: 7
И немного теории графов
Согласно спецификации контрольных измерительных материалов ОГЭ, задача 4 раскрывает такие понятия как:
Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра. Весовая матрица графа. Длина пути между вершинами графа. Поиск оптимального пути в графе. Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе. Вычисление количества путей в направленном ациклическом графе.
Рассмотрим данные термины.
Граф
Математическая структура, состоящая из множества вершин (узлов) и множества рёбер (соединений между вершинами). Граф может быть ориентированным или неориентированным.
Вершина
Основной элемент графа, точка или узел, в которых могут находиться объекты или состояния. Обозначается обычно буквой или числом.
Ребро
Соединение между двумя вершинами графа. В неориентированном графе ребро не имеет направления, в ориентированном — имеет направление (стрелку).
Путь
Последовательность вершин, где каждая пара соседних вершин соединена ребром. Путь может быть простым (без повторяющихся вершин) или с повторениями, в зависимости от условий задачи.
Ориентированные и неориентированные графы
- Неориентированный граф — граф, в котором рёбра не имеют направления. То есть, соединяющее вершины ребро считается одинаковым в обе стороны.
- Например: ребро между вершинами A и B — это одно и то же соединение, независимо от порядка.
- Ориентированный граф — граф, в котором рёбра имеют направление (стрелки). Каждое ребро — это дуга, указывающая от одной вершины к другой.
- Например: дуга из A в B означает, что движение возможно только в этом направлении.
Длина (вес) ребра
- Длина или вес ребра — числовое значение, которое может обозначать стоимость, расстояние, время или другую характеристику перехода между вершинами.
- Веса могут быть положительными или отрицательными (в некоторых задачах).
- Веса используются для поиска кратчайших путей, минимальных затрат и т.п.
Весовая матрица графа
Это матрица смежности, в которой элемент на позиции (i,j) — это вес ребра из вершины i в вершину j.
- Если ребра между вершинами нет, то обычно ставится ноль или бесконечность (зависит от реализации).
- Для ориентированного графа матрица может быть асимметричной; для неориентированного — симметричной.
Длина пути между вершинами графа
Длина пути — сумма весов всех рёбер, входящих в этот путь.
- В случае не взвешенного графа (все веса равны 1), длина пути — это просто количество рёбер в нем.
- Например, если путь из вершины A в вершину D через B и C: A → B → C → D, и веса рёбер: AB=2, BC=3, CD=4, то длина пути — 2+3+4=9.
Поиск оптимального пути в графе
Задача поиска оптимального пути — найти такой путь между двумя вершинами, у которого минимальна (или максимальна) длина или сумма весов.
В зависимости от задачи используют разные алгоритмы, например:
- Алгоритм Дейкстры — для поиска кратчайшего пути с неотрицательными весами.
- Алгоритм Беллмана-Форда — для графов с отрицательными весами.
- Алгоритм А* — для поиска путей с учетом эвристики.
Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе
- Источник (начальная вершина) — вершина, с которой начинается путь.
- Сток (конечная вершина) — вершина, в которую должен прийти путь.
В ориентированном графе поиск путей обычно ограничен направлением рёбер: путь должен следовать по стрелкам от источника к стоку.
Что такое направленный ациклический граф (DAG)?
- Направленный граф — граф, в котором рёбра имеют направление (стрелки).
- Ациклический — граф, в котором не существует циклов, то есть нельзя начать с вершины и пройти по рёбрам так, чтобы вернуться в исходную вершину.
Таким образом, DAG — это ориентированный граф без циклов.
И еще решение задач ОГЭ:
Подборка решений всех задач ОГЭ по информатике (пополняется)