ЕГЭ по информатике: Графы и кратчайшие пути
«Анализ графов и путей» — раздел блока «Теоретические основы информатики» кодификатора ФИПИ для профильного ЕГЭ по информатике (КЕГЭ, 2026), охватывающий одну из самых наглядных и в то же время требовательных к вниманию тем экзамена. Задания на графы проверяют умение читать матрицу смежности (или список рёбер с весами), находить кратчайший путь между вершинами (в духе алгоритма Дейкстры) и применять фундаментальные свойства деревьев — связных ациклических графов, где количество рёбер всегда на единицу меньше количества вершин.
Материал охватывает полный набор типовых задач: чтение и построение матрицы смежности/весов, поиск кратчайшего пути на графе из 4-5 вершин (как ориентированном, так и неориентированном), подсчёт степеней вершин, определение количества различных путей между двумя вершинами, и работу со свойствами деревьев (единственность пути между любыми двумя вершинами, эффект удаления/добавления ребра). Каждый граф задан текстом — списком рёбер с весами или явной матрицей смежности — прямо в условии вопроса, без ссылок на внешние изображения.
Дистракторы построены на реальных ошибках школьников при работе с графами: путанице вершин при переборе путей, неучёте более короткого пути через промежуточную вершину, арифметических ошибках при суммировании весов ребер вдоль маршрута. Отдельное внимание уделено тонкостям формальной логики — например, различию между «граф с n-1 рёбрами обязательно является деревом» (неверно без условия связности) и «дерево обязательно имеет n-1 рёбер» (верно всегда).
Тема будет полезна выпускникам, готовящимся к профильному ЕГЭ по информатике, а также студентам, начинающим изучать дискретную математику и алгоритмы на графах — базовое понимание кратчайших путей и свойств деревьев необходимо для дальнейшего освоения структур данных и сетевых алгоритмов. Флеш-карты закрепляют терминологию теории графов, свойства деревьев и логику алгоритма поиска кратчайшего пути.
- Читать и строить матрицу смежности/весов графа по текстовому описанию
- Находить кратчайший путь между вершинами взвешенного графа
- Определять степень вершины и подсчитывать количество различных путей
- Применять фундаментальные свойства деревьев
- Различать необходимые и достаточные условия для того, чтобы граф являлся деревом
- Подсчитывать количества различительных путей
Материал основан на блоке кодификатора ФИПИ 2026 «Теоретические основы информатики» (раздел «Графы») для профильного ЕГЭ по информатике (КЕГЭ) — все 10 вопросов оригинальные, без воспроизведения реальных заданий из открытого банка ФИПИ.