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

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

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

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

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

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

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

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

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

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

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

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

← Предыдущая тема: Задание 8. Компьютерные сети и поиск информации
Следующая тема: Задание 10. Системы счисления

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