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

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

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

Задание 23 проверяет умение решать алгоритмические задачи на графах: поиск кратчайшего пути или подсчёт количества путей в ориентированном ациклическом графе.
В экзаменационном варианте дан текстовый файл, где каждая строка содержит L, M, W — ребро из L в M с весом W (положительное вещественное число).
Вершины могут быть пронумерованы не подряд, номера до 1000, количество рёбер не более 200.
Требуется найти целую часть длины кратчайшего пути из вершины 1 в вершину 100 (или аналогичные номера).
Длина пути — сумма весов рёбер; ответ — целая часть (округление вниз, отбрасывание дробной части).
Граф ациклический, что позволяет использовать динамическое программирование по топологической сортировке или алгоритм Дейкстры.

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

Ориентированный граф: граф, в котором рёбра имеют направление (из L в M).
Ациклический граф: граф без циклов, что позволяет использовать топологическую сортировку.
Взвешенный граф: граф, каждому ребру которого сопоставлено число (вес).
Кратчайший путь: путь с минимальной суммой весов рёбер.
Целая часть числа: наибольшее целое, не превосходящее данное число (округление вниз).
Топологическая сортировка: упорядочивание вершин, при котором все рёбра идут от более ранних к более поздним.
Алгоритм Дейкстры: алгоритм поиска кратчайших путей из одной вершины во взвешенном графе с неотрицательными весами.
Динамическое программирование по графу: вычисление значений для вершин в порядке топологической сортировки.

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

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

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

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

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

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

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

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