ЕГЭ по информатике: Графы и кратчайшие пути

«Анализ графов и путей» — раздел блока «Теоретические основы информатики» кодификатора ФИПИ для ЕГЭ по информатике (КЕГЭ, 2026), охватывающий одну из самых наглядных и в то же время требовательных к вниманию тем экзамена. Задания на графы проверяют умение читать матрицу смежности (или список рёбер с весами), находить кратчайший путь между вершинами (в духе алгоритма Дейкстры) и применять фундаментальные свойства деревьев — связных ациклических графов, где количество рёбер всегда на единицу меньше количества вершин.

Материал охватывает полный набор типовых задач: чтение и построение матрицы смежности/весов, поиск кратчайшего пути на графе из 4-5 вершин (как ориентированном, так и неориентированном), подсчёт степеней вершин, определение количества различных путей между двумя вершинами, и работу со свойствами деревьев (единственность пути между любыми двумя вершинами, эффект удаления/добавления ребра). Каждый граф задан текстом — списком рёбер с весами или явной матрицей смежности — прямо в условии вопроса, без ссылок на внешние изображения.

Дистракторы построены на реальных ошибках школьников при работе с графами: путанице вершин при переборе путей, неучёте более короткого пути через промежуточную вершину, арифметических ошибках при суммировании весов ребер вдоль маршрута. Отдельное внимание уделено тонкостям формальной логики — например, различию между «граф с n-1 рёбрами обязательно является деревом» (неверно без условия связности) и «дерево обязательно имеет n-1 рёбер» (верно всегда).

Тема будет полезна выпускникам, готовящимся к ЕГЭ по информатике, а также студентам, начинающим изучать дискретную математику и алгоритмы на графах — базовое понимание кратчайших путей и свойств деревьев необходимо для дальнейшего освоения структур данных и сетевых алгоритмов. Флеш-карты закрепляют терминологию теории графов, свойства деревьев и логику алгоритма поиска кратчайшего пути.

  • Читать и строить матрицу смежности/весов графа по текстовому описанию
  • Находить кратчайший путь между вершинами взвешенного графа (в духе алгоритма Дейкстры)
  • Определять степень вершины и подсчитывать количество различных путей между вершинами
  • Применять фундаментальные свойства деревьев (число рёбер, отсутствие циклов, единственность пути)
  • Различать необходимые и достаточные условия для того, чтобы граф являлся деревом

Материал основан на блоке кодификатора ФИПИ 2026 «Теоретические основы информатики» (раздел «Графы») для ЕГЭ по информатике (КЕГЭ) — все 10 вопросов оригинальные, без воспроизведения реальных заданий из открытого банка ФИПИ.

Пример вопроса

Взвешенный неориентированный граф с вершинами 1–5 и рёбрами: 1–2 (вес 3), 2–3 (2), 2–4 (4), 3–4 (1), 3–5 (5), 4–5 (2).

Дан граф с вершинами {1, 2, 3, 4, 5}. Матрица смежности (где 0 — отсутствие ребра, число — вес): Строка 1: [0, 3, 0, 0, 0] Строка 2: [3, 0, 2, 4, 0] Строка 3: [0, 2, 0, 1, 5] Строка 4: [0, 4, 1, 0, 2] Строка 5: [0, 0, 5, 2, 0] Выберите все верные утверждения о путях из вершины 1 в вершину 5.

Показать ответ

Кратчайший путь имеет длину 8, Путь 1-2-4-5 имеет длину 9

Путь 1-2-3-4-5 имеет длину 3+2+1+2 = 8 — это и есть кратчайший путь. Путь 1-2-3-5 имеет длину 3+2+5 = 10. Путь 1-2-4-5 имеет длину 3+4+2 = 9. Пути длиной 5 не существует: из вершины 1 выходит только ребро 1–2 веса 3, а кратчайшее расстояние от 2 до 5 равно 5 (2–3–4–5), так что любой путь из 1 в 5 не короче 8. Не все пути проходят через вершину 3 — например, 1-2-4-5 обходит её.

Пройти этот тест →Повторить карточки →Выполнить письменную работу →

← Информатика

↑ ЕГЭ

ЕГЭ — государственный экзамен Российской Федерации; контрольные измерительные материалы к нему разрабатывает ФИПИ по заказу Рособрнадзора. Zestly не связана с ФИПИ и Рособрнадзором, не одобрена ими и не является официальным источником. Все задания написаны нами по открытому кодификатору и не воспроизводят материалы КИМ.