Графы и маршруты: что на самом деле проверяет задание
Графы и маршруты часто пугают выпускников, хотя задание проверяет не высшую математику, а умение мыслить шагами. В КИМ-ах важнее логику строить, чем помнить редкие теоремы. Экзаменаторы хотят увидеть, как ученик превращает текстовую историю в чёткую структуру «вершины-рёбра» и быстро находит нужный ответ. Первое, что стоит сделать: написать все номера вершин и выделить стартовую и целевую точки. Это снижает риски пропустить лишнее условие.
Парадоксально, но именно простые рисунки спасают время. Когда схема лежит перед глазами, мозг меньше перегружается переходами между абстракцией и черновиком. Дальше остаётся лишь выбрать подходящий алгоритм: перебор, поиск в ширину или рекурсивный подсчёт путей. Чтобы решить подзадачу за две-три минуты, важно заранее знать, какой приём сработает при конкретных ограничениях.
Термины без паники
Сети дорог, электрических цепей и социальные связи — всё это графы. В заданиях встречаются ориентированные и неориентированные модели. Первые учитывают направление, вторые — нет. Рёбра могут иметь вес. Число показывает стоимость, длину или время. Степень вершины — количество инцидентных рёбер. Путь — список вершин, где соседние связаны. Простым путь называют, если он не повторяет вершины. Цикл замыкается в исходной точке.
Важно различать связность графа. Связный неориентированный граф гарантирует, что добраться можно из любой вершины в любую. В ориентированном мире для того же свойства используют понятие сильной связности. Ещё одно частое слово — компонент. Оно означает максимальное множество вершин, связанных между собой.
Быстрые способы представления графа
Когда граф маленький, удобна матрица смежности. Таблица 10×10 помещается даже на стикере. Её плюс — проверка наличия ребра за O(1). Но память тратится много. Для разреженных графов лучше список смежности. Каждая строка хранит соседей вершины и меньше забивает лист.
Существуют гибридные варианты: хранят только верхний треугольник матрицы или используют словарь множеств. В ЕГЭ довольно графа из 20 вершин, поэтому выбранная структура почти не влияет на время работы, зато определяет удобство перебора.
Маршруты и подсчёт путей: три рабочих приёма
Первый приём — полный перебор с отсечением повторов. Подходит, когда количество вершин не превышает восемь. Второй — поиск в ширину. Он гарантирует кратчайший путь без весов. Третий — динамика по подмножествам или мемоизация рекурсии. При известной целевой вершине можно хранить число путей из каждой точки до финиша и пересчитывать снизу вверх.
- Перебор — проще написать, риск упереться во временной лимит.
- Поиск в ширину — стабильно находит минимум шагов.
- Динамика — спасает, когда просят количество различных маршрутов.
Главное — не смешивать задачи. Если спрашивают минимальную стоимость, нужен алгоритм Дейкстры, а не BFS. Для подсчёта вариантов Дейкстра бессильна. Чётко читайте условие и выбирайте инструмент.
Как избежать ловушек в формулировках
Разработчики любят прятать ограничения между строк. Читаем вопрос целиком, затем отмечаем маркером ключевые слова: «кратчайший», «строго меньше», «не допускается повторять». Ошибка часто возникает на фразе «можно посещать вершины не более одного раза». Это запрет на циклы, а не указание на простой путь по умолчанию.
Ещё одна ловушка — двойная нумерация. В задаче могут присутствовать и номера домов, и номера улиц. Создайте две таблицы соответствия, чтобы не спутать сущности. При подсчёте сумм весов держите в голове единицы измерения: километры, минуты, рубли. Приведите всё к одному формату, прежде чем складывать.
Тренажёр на Python за двадцать строк
Напишите функцию dfs(v, visited), которая возвращает количество путей до цели. Список sm для смежности храните во внешней области — так мемоизация проще. Внутри функции сразу проверяйте: если v==finish, верните 1. Затем переберите соседей, исключив уже посещённые. Результат cache[v] сохранит промежуточный счёт.
Чтобы потренироваться, создайте генератор графов. Случайно выводите количество вершин, затем подключайте rёbra с вероятностью p. Попросите программу выдать число путей от вершины 1 к вершине n. Меняйте p, пока не начнутся интересные случаи. Такой тренажёр вскрывает слабые места логики почти лучше сборников.
Экзаменационные лайфхаки из реальных вариантов
Вариант 2022 года показал непредвиденный массовый просчёт. Школьники забыли, что поиск в ширину даёт не только длину кратчайшего пути, но и сам маршрут. Поэтому многие искали путь повторно и тратили время. Используйте очередь, сохраняйте родителя каждой вершины и восстанавливайте ответ за O(L).
Часто дают условие «не проходить через вершины A и B одновременно». Решается удвоением графа. Создайте копии вершин с флагом посещения A. Рёбра переводят из одного слоя в другой, когда заходите в A. Метод кажется громоздким, но позволяет применить обычный поиск без модификаций.
Где прокачаться и не сгореть перед ЕГЭ
Становитесь сильнее, решая по одному графу ежедневно. Десять минут в день лучше, чем марафон ночью. Если нужен системный подход, загляните на онлайн курс подготовки к ЕГЭ. Там чёткая программа, тайм-менеджмент и проверка домашних, что экономит нервы.
Ставьте микроцели: сегодня изучаем веса, завтра — компоненты. После каждой темы решайте пару задач из открытого банка ФИПИ. Строго фиксируйте время решения. Позже сравните с целевыми тремя минутами. Постепенно скорость растёт, а стресс падает. Тогда на самом экзамене задание про графы станет приятной разминкой, а не источником паники.