Задание 23. Алгоритмические задачи на графы: ЕГЭ по информатике

Задание 23 ЕГЭ по информатике проверяет умение анализировать ориентированные графы: строить граф по описанию, находить количество различных путей между вершинами в ориентированном ациклическом графе, а также решать задачи построения оптимального пути (кратчайшего/наиболее выгодного) между…

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

Ориентированный граф: рёбра имеют направление, путь строится только по направлению рёбер.
Ациклический граф: отсутствуют циклы, что позволяет использовать динамическое программирование для подсчёта путей.
Количество путей из вершины-источника в вершину-сток: сумма количеств путей в predecessors (вершины, из которых есть ребро в данную).
Для подсчёта путей вершины нужно обрабатывать в топологическом порядке (от источника к стоку).
Если в графе есть циклы, подсчёт путей может быть бесконечным; в задании 23 обычно граф ациклический, но это нужно проверять.
Кратчайший путь в невзвешенном графе ищется обходом в ширину (BFS).

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

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

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

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

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

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

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

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

← Предыдущая тема: Задание 22. Математические модели и архитектура компьютеров
Следующая тема: Задание 24. Обработка символьных данных

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