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

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

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

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

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

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

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

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

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

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

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

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

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

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