Задание 4. Графы и поиск путей: ОГЭ по информатике

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

Что нужно знать

Граф состоит из вершин и рёбер; ребро может быть ориентированным (дуга) или неориентированным.
Путь — последовательность вершин, где каждая пара соседних соединена ребром; длина пути — число рёбер (для невзвешенного) или сумма весов (для взвешенного).
В ориентированном графе путь должен учитывать направление рёбер.
Весовая матрица графа: таблица, где на пересечении строки i и столбца j стоит вес ребра из i в j; если ребра нет, то обычно 0 или бесконечность (в условии уточняется).
Матрица смежности: 1 — есть ребро, 0 — нет; для неориентированного графа матрица симметрична.
Кратчайший путь в взвешенном графе ищется алгоритмом Дейкстры (если веса неотрицательны) или перебором для малых графов.

Термины и понятия

Граф: совокупность вершин и соединяющих их рёбер.
Вершина: точка графа, обозначающая объект.
Ребро: линия, соединяющая две вершины; может быть ориентированным (дугой) или неориентированным.
Путь: последовательность вершин, где каждая пара соседних соединена ребром.
Длина пути: количество рёбер в пути (для невзвешенного графа) или сумма весов рёбер (для взвешенного).
Ориентированный граф: граф, в котором рёбра имеют направление.
Неориентированный граф: граф, в котором рёбра не имеют направления.
Весовая матрица: таблица, где элемент (i,j) равен весу ребра из вершины i в вершину j.

Частые ошибки

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

Как пройти тему

В курсе «Информатика» тема «Задание 4. Графы и поиск путей» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Задание 3. Логические высказывания и таблицы истинности
Следующая тема: Задание 5. Анализировать простые алгоритмы для конкретного исполнителя с фиксированным набором команд

Все темы: ОГЭ по информатике