Краткий ответ
Задание 1 ЕГЭ по информатике — это подсчёт количества путей в ориентированном графе («схема дорог, по каждой дороге можно двигаться только в одном направлении, указанном стрелкой»). Универсальный способ решения — динамическое программирование по вершинам: у стартовой вершины число путей равно 1, у каждой следующей — сумма чисел путей всех вершин, из которых в неё входят стрелки. Дополнительные условия («через город X», «не проходя через Y») учитываются тем же аппаратом.
1. Понятия, которые нужно держать в голове
- Граф — набор вершин (городов, пунктов) и рёбер (дорог) между ними.
- Ориентированный граф (орграф) — у каждого ребра есть направление, это дуга. На схеме показывается стрелкой.
- Путь из A в B — последовательность вершин \(A = v_0, v_1, \dots, v_k = B\), в которой каждая соседняя пара соединена дугой в нужном направлении.
- Длина пути — количество дуг в нём (а не количество путей!).
- Различные пути различаются порядком вершин, даже если длина у них одинаковая.
В задании 1 граф почти всегда без циклов: стрелки идут «в одну сторону», поэтому путей конечное число и их можно честно посчитать.
Иногда граф дан не рисунком, а таблицей (матрицей смежности): если в строке \(i\) и столбце \(j\) стоит 1, значит есть дуга из \(i\) в \(j\).
2. Главная идея: динамическое программирование
Пусть \(f(v)\) — число путей из стартовой вершины \(A\) в вершину \(v\). Тогда:
\[ f(A) = 1, \qquad f(v) = \sum_{u \to v} f(u) \ \text{ для всех } v \neq A, \]
где суммирование идёт по всем вершинам \(u\), из которых есть дуга \(u \to v\).
Смысл простой: чтобы попасть в \(v\), путь должен последним шагом прийти из какого-то «входа» \(u\); каждый путь в \(u\) даёт ровно один путь в \(v\).
Важно: считать нужно в топологическом порядке — вершину обрабатываем только тогда, когда все её «входы» уже посчитаны.
3. Порядок действий (алгоритм)
- Выписать все дуги графа (или все единицы матрицы).
- Упорядочить вершины так, чтобы все стрелки шли «вперёд». Если все стрелки на схеме идут слева направо по столбцам — просто идём по столбцам.
- Завести таблицу \(f\), положить \(f(A) = 1\).
- Идти по вершинам в выбранном порядке и для каждой считать сумму по входящим дугам.
- Ответ — \(f(B)\), где \(B\) — конечная вершина.
4. Пример с полной проверкой
Города А, Б, В, Г, Д, Е. Дороги (со стрелками): А→Б, А→В, Б→В, Б→Г, В→Г, В→Д, Г→Е, Д→Е. Сколько путей из А в Е?
Порядок: А, Б, В, Г, Д, Е.
| Вершина | Входящие дуги | Расчёт | \(f\) |
|---|---|---|---|
| А | — | старт | 1 |
| Б | А→Б | 1 | 1 |
| В | А→В, Б→В | 1 + 1 | 2 |
| Г | Б→Г, В→Г | 1 + 2 | 3 |
| Д | В→Д | 2 | 2 |
| Е | Г→Е, Д→Е | 3 + 2 | 5 |
Ответ: 5 путей.
Проверка «с конца»: пусть \(g(v)\) — число путей из \(v\) в Е.
\[ g(\text{Е}) = 1,\quad g(\text{Д}) = 1,\quad g(\text{Г}) = 1, \] \[ g(\text{В}) = g(\text{Г}) + g(\text{Д}) = 2,\quad g(\text{Б}) = g(\text{В}) + g(\text{Г}) = 3, \] \[ g(\text{А}) = g(\text{Б}) + g(\text{В}) = 5. \]
Совпало — 5. Такая обратная проверка ловит почти все ошибки в подсчёте.
5. Дополнительные условия в задании 1
«Путь проходит через город C». Считаем дважды: \[ N = f(C) \cdot g(C), \] где \(f(C)\) — число путей из А в C, \(g(C)\) — число путей из C в B. В примере выше через Г: \(3 \cdot 1 = 3\).
«Путь не проходит через C». Удалить вершину C вместе со всеми её дугами и посчитать заново (или из общего числа вычесть пути через C).
«Проходит ровно через один из городов C или D». Считать отдельно «через C» и «через D», а пути, идущие через оба, посчитать отдельно и не забыть, что они попали в оба слагаемых — аккуратно вычесть.
Запрещённая вершина как промежуточная. В таблице ставим \(f = 0\) для неё (но только если она не старт и не финиш).
Если в графе есть цикл — ДП «в лоб» не работает, нужен перебор или другой подход. В реальных вариантах задания 1 циклов не бывает.
6. Типичные ошибки
- Забыли, что \(f(A) = 1\), а не 0.
- Пропустили входящую дугу при суммировании (особенно «длинную», перечёркивающую схему).
- Посчитали вершину раньше, чем все её входы (нарушили порядок).
- Перепутали количество путей с длиной пути.
- В условии «через C» умножили, но взяли \(f\) и \(g\) не от той вершины.
- Сложили вместо умножения (или наоборот) при подсчёте «через вершину».
7. Что ещё полезно помнить
- Для взвешенного графа (у дорог указаны длины) задача «кратчайший путь» решается алгоритмом Дейкстры или перебором — это другой тип задачи, в актуальном задании 1 его нет, но путать формулировки не стоит.
- Число путей растёт быстро: если ответ получился «подозрительно маленьким» при ветвистом графе — перепроверьте таблицу.
- Время на задание 1 — 2–4 минуты; аккуратная таблица \(f\) быстрее, чем перебор путей «руками».