Задание 9 ОГЭ: подсчёт путей между городами по схеме дорог

Что проверяет задание

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

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

Как выглядит формулировка и сколько баллов

Типичная формулировка: «На рисунке — схема дорог, связывающих города А, Б, В, ... По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К (Л)?»

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

Что нужно знать

• Граф — совокупность вершин (городов) и рёбер (дорог) между ними.
• Ориентированный граф — граф, в котором рёбра имеют направление (можно двигаться только по стрелке, в обратную сторону — нельзя).
• Путь из вершины $A$ в вершину $B$ — последовательность рёбер, ведущая от $A$ к $B$ по направлению стрелок, без повторения вершин (циклы в схемах ОГЭ обычно не встречаются).
• Правило суммы: если в вершину $X$ можно попасть только из вершин $P_1, P_2, \dots, P_k$, то количество путей до $X$ из начальной точки равно сумме количеств путей до каждой из этих вершин: $$N(X) = N(P_1) + N(P_2) + \dots + N(P_k)$$
• Начальной вершине присваивается значение $N(A) = 1$ (существует ровно один "путь" — остаться на месте / начать движение).
• Если в вершину нет входящих рёбер (кроме старта), она недостижима, и $N = 0$.
• Вершины нужно обрабатывать в порядке топологической сортировки — то есть только после того, как посчитаны значения для всех вершин, из которых в неё ведут стрелки.
• Для подсчёта путей, проходящих через определённый пункт $C$, используется умножение: число путей из $A$ в $B$ через $C$ равно произведению числа путей из $A$ в $C$ и числа путей из $C$ в $B$: $$N(A \to B \text{ через } C) = N(A \to C) \cdot N(C \to B)$$
• Число путей, не проходящих через $C$, находится как разность общего числа путей и числа путей, проходящих через $C$: $$N(A \to B \text{ мимо } C) = N(A \to B) - N(A \to B \text{ через } C)$$

Методы решения

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

Мини-пример. Пусть из $A$ есть стрелки в $B$ и $C$, а из $B$ и $C$ — по стрелке в $D$. Тогда $N(A)=1$, $N(B)=1$, $N(C)=1$, $N(D) = N(B) + N(C) = 1+1=2$. Итого 2 пути из $A$ в $D$.

Метод 2. Разбиение схемы на уровни (ярусы). Полезно перерисовать граф так, чтобы вершины были расположены по "уровням" — по расстоянию (числу шагов) от старта. Это помогает не запутаться в порядке обработки и не забыть какую-то вершину.

Мини-пример. Если из $A$ можно попасть в $B$ и $C$ за один шаг, а в $D$ — только через $B$ и $C$, то уровень 0 — это $A$, уровень 1 — $B, C$, уровень 2 — $D$. Считаем строго по уровням слева направо.

Метод 3. Подсчёт путей через фиксированный пункт (умножение). Чтобы найти число путей из $A$ в $K$, проходящих через город $C$, отдельно считаем число путей из $A$ в $C$ (назовём $p$) и число путей из $C$ в $K$ (назовём $q$), затем умножаем: $p \cdot q$.

Мини-пример. Если из $A$ в $C$ ведут 3 пути, а из $C$ в $K$ — 2 пути, то через $C$ проходит $3 \cdot 2 = 6$ путей из $A$ в $K$.

Метод 4. Подсчёт путей, минующих определённый пункт (вычитание или прямой пересчёт без учёта вершины). Есть два способа: либо вычесть из общего числа путей число путей через нужный пункт, либо временно "удалить" вершину-пункт из схемы (не учитывать рёбра, входящие и исходящие из неё) и пересчитать пути заново по методу 1.

Мини-пример. Если всего из $A$ в $K$ идёт 10 путей, а через $C$ — 6, то мимо $C$ проходит $10-6=4$ пути.

Метод 5. Проверка через симметрию или альтернативный маршрут (для самоконтроля). После получения ответа полезно посчитать число путей другим способом — например, идя от конечной вершины назад к начальной (присвоить конечной вершине 1 и суммировать в обратном направлении по исходящим рёбрам). Если результаты совпали — расчёт верен.

Алгоритм решения по шагам

1. Внимательно рассмотреть схему, выписать все вершины (города) и все рёбра со стрелками направления.
2. Определить стартовую и конечную вершину задачи.
3. Присвоить стартовой вершине число путей, равное 1.
4. Определить порядок обработки остальных вершин: вершина обрабатывается только тогда, когда обработаны все вершины, из которых в неё есть стрелка (топологический порядок, обычно совпадает с порядком "слева направо" на схеме).
5. Для каждой вершины найти все входящие в неё стрелки, определить вершины-источники, сложить их значения — это и есть число путей до текущей вершины.
6. Дойти до конечной вершины и записать итоговое число — это ответ на вопрос "сколько всего путей".
7. Если в задаче требуется учесть определённый пункт (пройти через него или миновать), выполнить дополнительный шаг: посчитать пути от старта до этого пункта и от пункта до финиша отдельно, затем перемножить (для "через") или вычесть из общего числа (для "мимо").
8. Проверить результат: пересчитать хотя бы одну "развилку" повторно или выполнить обратный подсчёт от конечной вершины к начальной.

Разбор примеров

Пример 1. Схема дорог связывает города А, Б, В, Г, Д, Е, Ж, З, И, К, Л; движение по каждой дороге одностороннее (по стрелке). Найти число различных путей из А в Л.

Решение по шагам:

1. Присваиваем $N(A) = 1$.
2. Обрабатываем вершины в порядке, в котором все их "источники" уже посчитаны — то есть двигаемся от А к Л, шаг за шагом суммируя значения вершин, из которых есть стрелка в текущую вершину.
3. Для каждой промежуточной вершины (Б, В, Г, Д, Е, Ж, З, И, К) складываем значения тех вершин, откуда в неё идёт дорога — согласно конкретной конфигурации стрелок на рисунке.
4. Продолжаем расчёт до тех пор, пока не дойдём до вершины Л, суммируя значения всех вершин, из которых есть прямая дорога в Л.
5. Итоговое значение, полученное для Л, — это искомое количество путей.

После выполнения всех промежуточных сложений в соответствии со схемой получаем: $$N(Л) = 22$$ Ответ: 22.

Пример 2. Схема связывает города А, Б, В, Г, Д, Е, К (движение одностороннее). Найти число путей из А в К.

Решение по шагам:

1. $N(A) = 1$ — стартовая вершина.
2. Так как городов немного, удобно последовательно посчитать значение для каждой вершины по порядку удалённости от А: сначала вершины, куда ведёт стрелка прямо из А, затем следующие.
3. Для каждой вершины (Б, В, Г, Д, Е) суммируем значения всех вершин-источников, из которых в неё есть дорога — в соответствии с расположением стрелок на схеме.
4. Последней обрабатываем вершину К, суммируя значения всех вершин, из которых есть дорога непосредственно в К.
5. Итоговая сумма даёт: $$N(К) = 6$$ Ответ: 6.

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

Пример 3. Схема связывает города А, Б, В, Г, Д, Е, Ж, З, И, К, Л (движение одностороннее). Найти число путей из А в Л.

Решение по шагам аналогично примеру 1:

1. $N(A) = 1$.
2. Последовательно, в порядке топологической сортировки схемы, вычисляем значения для всех промежуточных городов, суммируя значения вершин-источников для каждой вершины согласно направлению стрелок.
3. Особое внимание уделяем вершинам с несколькими входящими дорогами — там легко забыть один из слагаемых.
4. Доходим до вершины Л и складываем значения всех вершин, из которых есть прямая дорога в Л.
5. Получаем: $$N(Л) = 19$$ Ответ: 19.

Сравнение примеров 1 и 3 показывает: при похожей структуре схемы (одинаковый набор городов) итоговое число путей может отличаться в зависимости от конкретного расположения стрелок — поэтому решать такие задачи "по аналогии" без построения расчёта для конкретной картинки нельзя, каждую схему нужно разбирать заново.

Типичные ошибки и ловушки

• Пропуск одной из входящих стрелок. Самая частая ошибка — забыть, что в вершину ведёт не одна, а две или три дороги, и просуммировать не всё.
• Нарушение порядка обработки вершин. Если посчитать значение вершины раньше, чем посчитаны значения всех её источников, результат окажется неверным (в сумму попадёт не всё, что нужно).
• Путаница направления стрелки. Легко перепутать, куда идёт дорога — из А в Б или из Б в А. Перед расчётом стоит явно выписать список рёбер с указанием направления.
• Учёт "обратного" движения. Поскольку дороги односторонние, нельзя использовать дорогу в обратном направлении, даже если визуально это выглядит как короткий путь.
• Ошибка при задачах "через" или "мимо" пункта. Часто путают, что нужно умножать (путь через пункт), а что вычитать (путь мимо пункта). Нужно чётко разделять эти две ситуации.
• Пропуск транзитных вершин с одним входом и одним выходом. Если вершина имеет всего одну входящую и одну исходящую дорогу, число путей до неё просто равно числу путей до её источника — такие вершины не увеличивают число вариантов, но их всё равно нельзя пропускать при построении цепочки.
• Арифметические ошибки при сложении большого количества слагаемых — на сложных схемах с 10+ городами легко ошибиться при устном подсчёте суммы, поэтому стоит записывать промежуточные значения рядом с каждой вершиной на схеме.

Как готовиться

• Тренируйтесь перерисовывать схему из условия на черновик, подписывая рядом с каждой вершиной промежуточное число путей — это резко снижает число ошибок.
• Всегда выписывайте список рёбер (например, «А→Б, А→В, Б→Г, В→Г») перед началом расчёта, чтобы не потерять ни одной дороги при работе непосредственно по картинке.
• Решайте задачи разного уровня сложности: с 5–7 городами и с 10–11 городами, чтобы приноровиться к разным по размеру схемам.
• Отдельно потренируйтесь на задачах "через определённый пункт" и "мимо определённого пункта" — важно автоматически знать, где умножать, а где вычитать.
• После решения проверяйте себя обратным способом: посчитайте пути от конечной вершины к начальной (по обратным правилам) и убедитесь, что число совпало.
• Держите под рукой правило суммы и правило произведения — они являются базой для всех вариаций этого задания, и уверенное владение ими избавляет от необходимости запоминать частные случаи.
• Разбирайте разобранные в этом гайде примеры самостоятельно, вручную повторяя каждый шаг расчёта — механическое повторение алгоритма формирует автоматизм, необходимый на экзамене при ограничении по времени.