Графы и маршруты: лайфхаки для экзамена

Как за 5 шагов перевести условие в таблицу

** изображение создано или обработано с помощью ИИ.

Я несколько лет разбираю задачи по графам со школьниками. Сам когда-то путал путь с маршрутом. Было стыдно, но полезно.

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

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

Я говорю ученикам: не решайте картинку глазами. Глаза обманывают, особенно в таблицах и схемах. Рука с карандашом работает честнее. Выпишите вершины, связи и ограничения на бумагу. Потом считайте.

Важный момент: экзамен использует одни и те же слова в разных значениях. Маршрут, путь, цепь, цикл — не синонимы. Если в условии дан точный термин, держитесь его. Если термин бытовой — смотрите на ограничения. Можно повторять вершины? А рёбра? Ответ меняется полностью.

Краткий чек-лист перед решением:

1. вершины перечислены;

1. рёбра (с направлениями или без) записаны;

1. веса (если есть) выписаны отдельно;

1. ограничения на повторы вершин и рёбер поняты;

1. что именно нужно найти (количество, длину, факт существования) зафиксировано.

Как читать схему и таблицу: инвентаризация графа

** изображение создано или обработано с помощью ИИ.

Начинайте не с подсчётов, а с инвентаризации. Смешно звучит — будто склад проверяем. Но граф действительно любит порядок.

Сначала запишите все вершины списком. Затем отметьте рёбра. Если граф ориентированный — поставьте стрелки. Если нет — не придумывайте направление.

Для маленького графа удобен список смежности. Рядом с вершиной А пишете В, С, D. Это значит: из А есть связь с этими точками. Такой список проверяется быстрее хаотичной схемы.

Если дана таблица, смотрите на заголовки строк и столбцов. В матрице смежности единица обычно обозначает связь, ноль — её отсутствие. В матрице весов вместо единицы стоят длины или стоимости. Пустые клетки часто означают запрещённый переход.

Если таблица без названий? Тогда сравнивайте степени вершин. Степень — число рёбер, касающихся вершины. В неориентированном графе петлю считают дважды. На школьных экзаменах петли редки, но правило помнить полезно.

Быстрая проверка для неориентированного графа: сумма степеней всех вершин равна удвоенному числу рёбер. Не магия, а учёт: каждое ребро касается двух концов. Если сумма степеней нечётная — ошибка.

На черновике используйте один стиль отметок. Пройденные рёбра зачёркивайте. Посещённые вершины обводите. Веса подписывайте отдельно. Не смешивайте всё в одну кашу. Мозг на экзамене и так работает в режиме «спасаемся».

Маршрут, путь, цикл: где прячется ловушка

** изображение создано или обработано с помощью ИИ.

Маршрут — последовательность вершин, где соседние соединены ребром. В маршруте обычно разрешены повторы вершин и рёбер. Если условие не запрещает повторы — не выдумывайте запрет. Экзамен ловит именно на этом.

Цепь — маршрут без повторяющихся рёбер. Вершины при этом могут повторяться. Путь — маршрут без повторяющихся вершин. Раз вершины не повторяются, рёбра автоматически тоже уникальны. Цикл начинается и заканчивается в одной вершине, остальные внутри не повторяются.

— Можно вернуться в ту же точку?

— Можно, если вы ищете цикл или маршрут.

— А если путь?

— Тогда нет.

Когда считаете количество маршрутов, помогает динамика по шагам. Делаете таблицу: где можно оказаться после первого, второго, третьего шага. На каждом шаге обновляете числа по рёбрам. Это проще, чем рисовать дерево вариантов.

Если условие требует «ровно N дорог» — считайте рёбра, не вершины. Маршрут из трёх рёбер содержит четыре посещения вершин. Я видел, как сильные ученики теряли балл на этой мелочи.

Для путей без повторов нужна аккуратность. Нельзя просто перемножить варианты. После каждого выбора граф меняется: вершина использована, часть переходов исчезла. Я ставлю крестик у таких точек на черновике.

В задачах на циклы проверьте стартовую вершину. Иногда цикл можно начать в любой точке одного и того же обхода. Тогда один и тот же цикл посчитают несколько раз. Если требуется число разных циклов — уточняйте логику подсчёта по условию. Иначе получите ответ в два раза больше.

Алгоритмы для ЕГЭ: что реально нужно знать

** изображение создано или обработано с помощью ИИ.

Не нужен полный университетский курс, достаточно нескольких приёмов.

1. Поиск в ширину (BFS) находит кратчайшее число рёбер от стартовой вершины в невзвешенном графе. Работает как волна: от начальной точки расходится по соседям.

1. Поиск в глубину (DFS) помогает проверять связность, находить компоненты и перебирать варианты. Это как прогулка по коридорам: идёте, пока можете, упираетесь — возвращаетесь назад.

1. Алгоритм Дейкстры ищет кратчайшие расстояния от одной вершины во взвешенном графе. Важно: веса рёбер не должны быть отрицательными. На базовых экзаменационных задачах отрицательные веса почти не встречаются, но условие читайте внимательно.

1. Дейкстру можно выполнять руками. Заведите таблицу расстояний. Стартовой вершине поставьте 0, остальным — бесконечность (или большой прочерк). На каждом шаге выбирайте непосещённую вершину с минимальной текущей оценкой, затем улучшайте расстояния до её соседей.

1. Подсчёт маршрутов с ограниченным числом шагов удобно делать динамически. Из каждой вершины распределяйте количество способов к соседям. После нужного шага смотрите значение в целевой вершине. Метод надёжный и спокойный.

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

Если хотите тренироваться системно, посмотрите курс подготовки к ЕГЭ в онлайн-школе. Расписание и проверка ошибок экономят время. Самостоятельность хороша, но дедлайн иногда лечит лучше витаминов.

Типовые задачи и быстрые проверки

** изображение создано или обработано с помощью ИИ.

Первый — восстановить граф по таблице. Не спешите рисовать красиво. Сначала отметьте степени вершин. Уникальные степени часто сразу выдают нужные точки на схеме. Если степени совпали, смотрите на соседей.

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

Третий — посчитать количество маршрутов. Помогает таблица шагов. В строках — номер шага, в столбцах — вершины. В начальной вершине на шаге 0 ставьте 1. Как это выглядит на черновике: Старт в A, цель в D. Шаг 0: A=1, остальные 0. Шаг 1: из A идут в B и C, значит B=1, C=1. Шаг 2: из B в D, из C в D, значит D=1+1=2. Ответ: 2 маршрута длины 2. Таблица не даёт потеряться в ветках.

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

Пятый — выбрать минимальную сеть (минимальное остовное дерево). Нужно соединить все вершины с минимальной суммой длин рёбер. Для ручного решения берите самые дешёвые рёбра по порядку, но не замыкайте цикл раньше времени.

Мой чек-лист перед ответом:

1. Тип графа определён (ориентированный / неориентированный / взвешенный).

1. Вершины и связи выписаны отдельно от рисунка.

1. Разрешены ли повторы вершин и рёбер — проверено.

1. Ответ сопоставлен с простыми ограничениями задачи.

1. Если осталась минута — проверка другим способом.

Последний пункт не роскошь. Ответ «17 маршрутов» можно быстро проверить чётностью или на маленькой таблице. Если граф симметричен, результаты для похожих вершин часто совпадают. Несовпадение — не всегда ошибка, но повод насторожиться.

Частые вопросы перед экзаменом

** изображение создано или обработано с помощью ИИ.

Перед экзаменом вопросы повторяются. Я слышал их десятки раз, иногда одним и тем же дрожащим голосом. Разберём самые живучие.

Что важнее: теория или практика? Баланс. Теория даёт язык для описания задачи. Практика учит замечать ловушки. Без терминов вы не поймёте условие. Без задач термины останутся красивыми наклейками.

Как не путать путь и маршрут? Запомните жёстко: путь не повторяет вершины. Маршрут может повторять. Если в условии разрешены повторы — путь уже не подходит.

Когда использовать таблицу шагов? Для подсчёта маршрутов фиксированной длины. Особенно когда спрашивают «за 4 хода» или «ровно за 5 дорог». Дерево вариантов быстро разрастается, таблица остаётся компактной.

Можно ли решать без рисунка? Да, если дана таблица. Но небольшой набросок часто помогает. Только не украшайте его. Экзамен — не конкурс плакатов.

Что делать с ориентированным графом? Идите только по стрелкам. Обратный ход нельзя использовать без явного ребра в обратную сторону. Это частая причина лишних маршрутов в ответе.

Как проверить задачу на обход всех рёбер? Посчитайте вершины с нечётной степенью. Для эйлерова цикла их должно быть ноль. Для эйлерова пути — ровно две.

Нужно ли учить Дейкстру? Да, хотя бы ручную версию с таблицей расстояний. Она часто помогает в задачах с весами. Главное — не выбирайте вершину наугад на каждом шаге.

Не пытайтесь угадать ответ по виду схемы. Графы кажутся лёгкими, пока не начнёшь считать. Зато они честные. Если аккуратно выписать связи, зафиксировать ограничения и вести таблицу — задача обычно сдаётся без боя. А если не сдаётся, сделайте вдох. Даже граф иногда просто хочет внимания.