Графы и поиск путей: разбор для ЕГЭ

Понятный старт: что такое граф и зачем он нужен на ЕГЭ

Задачи на графы приносят стабильные первичные баллы на ЕГЭ по информатике, но из-за невнимательности школьники теряют здесь до 15% результата. В этой статье мы по шагам разберем теорию, сопоставление таблиц со схемами и алгоритм подсчета путей, чтобы ты решал эти номера за пару минут без ошибок.

Граф — это математическая модель, состоящая из точек (вершин) и соединяющих их линий (рёбер). Если по линии можно двигаться только в одном направлении, её называют направленным ребром или дугой, а сам граф — ориентированным. В кодификаторе ЕГЭ графы встречаются в двух ключевых заданиях:

Задание 1: сопоставление весовой матрицы (таблицы расстояний) и неориентированного графа.
Задание 13: поиск количества различных путей в ориентированном графе с дополнительными условиями.

Главная характеристика вершины — её степень. Степень вершины равна числу ребер, которые с ней соединены. Если граф ориентированный, то у каждой вершины есть полустепень захода (число входящих стрелок) и полустепень исхода (число выходящих стрелок). Понимание этих свойств позволяет быстро разгадывать соответствие между таблицей и рисунком.

Матрица смежности: как сопоставить таблицу и схему

В первом задании ЕГЭ схема дорог и таблица протяженности составлены независимо. Номера пунктов в таблице (П1, П2, ...) перепутаны, и твоя задача — сопоставить буквы на схеме с номерами строк и столбцов. Для этого используется матрица смежности или весовая таблица.

Пункт	П1	П2	П3	П4	П5	Степень
П1		12		15		2
П2	12		10		20	3
П3		10			8	2
П4	15				14	2
П5		20	8	14		3

Чтобы быстро сопоставить таблицу с рисунком, придерживайся чёткого алгоритма:

Шаг 1. Посчитай степень каждой вершины на схеме и в таблице.
Шаг 2. Найди уникальные вершины (например, единственную вершину со степенью 3 или 4).
Шаг 3. Анализируй окружение: смотри, с какими соседями связана нужная вершина.
Шаг 4. Выпиши длины ребер и найди искомый ответ.

Если хочешь отработать этот навык на свежих задачах из банка ФИПИ, открой бесплатный тренажёр «Просто Урок», где собраны типовые прототипы с автоматической проверкой ответов.

Подсчёт путей: метод динамического программирования

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

Суть метода: количество способов добраться до вершины V равно сумме способов добраться до всех вершин, из которых в V ведут стрелки. Для начального пункта значение всегда принимается равным 1.

Базовое условие: N(Старт) = 1.
Для любой вершины V: N(V) = N(U₁) + N(U₂) + ... + N(Uₖ),
где U₁, U₂, ..., Uₖ — все вершины, из которых есть стрелка в V.

Пошаговое заполнение значений исключает механические ошибки. Главное — аккуратно отслеживать каждую стрелку на бланке.

Разбор типового задания с ограничениями

На реальном экзамене редко просят найти просто все пути. Обычно формулировка содержит дополнительные условия: маршрут обязан проходить через город В и при этом не должен проходить через город Ж.

Задача: Найти количество путей из А в М, проходящих через В и не проходящих через Ж.
Этап 1: Исключаем запрещенный пункт Ж. Аккуратно вычеркиваем вершину Ж и все входящие и выходящие из неё стрелки.
Этап 2: Учитываем обязательный пункт В. Любой путь обязан пройти через В. Значит, все ребра, которые идут в обход В к последующим вершинам, нужно удалить.
Этап 3: Считаем значения вершин:
\( N(\text{А}) = 1 \)
N(Б) = N(А) = 1
N(В) = N(А) + N(Б) = 1 + 1 = 2
N(Г) = N(В) = 2 (ветку А → Г вычеркнули, так как она идет в обход В)
N(Д) = N(В) + N(Г) = 2 + 2 = 4
N(Е) = N(В) + N(Д) = 2 + 4 = 6
N(М) = N(Д) + N(Е) = 4 + 6 = 10

Чек-лист для самопроверки на экзамене

Чтобы получать максимальный балл за задачи на графы, выработай привычку выполнять самопроверку по шагам. На экзамене важна не только скорость, но и дисциплина оформления черновика.

Используй следующий алгоритм проверки:

1. В задании 1 пересчитай сумму длин ребер в строке таблицы и сравни со степенью вершины на чертеже.
2. Проверь симметричность матрицы: расстояние от П1 до П2 обязано совпадать с расстоянием от П2 до П1.
3. В задании 13 проверь, что каждая входящая стрелка учтена ровно один раз при сложении.
4. Убедись, что вычеркнуты все обходные пути, если в условии есть обязательный пункт.

Ты можешь практиковать решение таких номеров на время. В личном кабинете «Просто Урок» доступны тематические подборки задач, которые помогают развить внимательность и закрепить алгоритм до автоматизма.

Что запомнить и как тренироваться

Графы в ЕГЭ по информатике — это гарантированные баллы при условии системного подхода. Запомни три главных правила для успешного решения:

— Матрицы и схемы: опирайся на степени вершин и уникальные связки соседей.
— Динамика путей: стартуй с 1, складывай входящие стрелки, вычисляй только готовые вершины.
— Дополнительные условия: вычеркивай запрещенные вершины и срезай обходные ветки до начала суммирования.

Закрепи разобранные методы на практике. Перейди в личный кабинет «Просто Урок» и реши 5 тренировочных заданий на графы прямо сейчас, чтобы быть уверенным в своем результате на экзамене.