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

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

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

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

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

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

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

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

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

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

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

• Задание 1. Информационный объём данных и единицы измерения
• Задание 2. Кодирование текстов, алфавитный подход, равномерный и неравномерный код
• Задание 3. Логические высказывания и логические операции
• Задание 4. Графы, пути и количество путей
• Задание 5. Анализ работы алгоритма по входным и выходным данным
• Задание 6. Программирование: переменные, ветвления, циклы, типовые алгоритмы

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

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