Задание 9 ОГЭ по информатике: количество путей по схеме дорог

• Вершины — города (кружочки с буквами). Рёбра — дороги. Фраза «по каждой дороге можно двигаться только в одном направлении, указанном стрелкой» означает, что все рёбра ориентированные: это орграф, а дорога — дуга со строгим направлением.
• Начальная вершина (источник) — город, из которого выезжаем; конечная вершина (сток) — город, в который надо попасть. Эти термины прямо взяты из кодификатора.
• Путь — последовательность городов, где каждый следующий достижим по стрелке из предыдущего. Два пути различны, если различаются последовательностью городов. Путь «А — Б — К» и путь «А — В — Г — Е — К» считаются наравне: длина маршрута никакой роли не играет.
• Схема в задании 9 — направленный ациклический граф: по стрелкам нельзя вернуться в город, где вы уже были. Это существенно: будь на схеме цикл, по кольцу можно было бы наматывать сколько угодно кругов и путей стало бы бесконечно много. Именно ацикличность гарантирует, что ответ — конечное число, и именно она делает корректным приём, описанный ниже.
• Из ацикличности следует, что города можно перенумеровать так, чтобы все стрелки шли «вперёд» (топологический порядок). А значит, найдётся порядок обхода, в котором у каждого города все его «предшественники» будут посчитаны раньше него самого.

Обозначим через $N(X)$ количество различных путей из стартового города в город $X$. Весь метод — два правила.

Правило 1 (база). В стартовом городе пишем единицу:

Это не «ноль путей» и не «сколько дорог выходит из А». В стартовый город ведёт ровно один «пустой» путь — вы уже там. Если поставить 0, весь граф обнулится.

Правило 2 (переход). Число в городе — сумма чисел всех городов, из которых в него ведёт стрелка:

где $Y_1, Y_2, \dots, Y_k$ — все города, из которых есть дуга $Y_i \to X$. Логика простая: каждый путь в $X$ обязан прийти по одной из входящих дорог, и такие наборы путей не пересекаются — значит, количества складываются.

Правило 3 (порядок). Город считаем только тогда, когда посчитаны все города с входящими в него стрелками.

Это самое важное практическое правило. Если хотя бы у одного «поставщика» числа ещё нет — город пропускаем и вернёмся к нему позже. Схемы ФИПИ обычно нарисованы слоями слева направо, и порядок «слева направо, сверху вниз» чаще всего совпадает с нужным, но опираться надо именно на правило, а не на картинку: длинные дуги «через весь рисунок» ломают наивный порядок.

Маленький пример целиком

Пусть на схеме шесть дорог (запись «А → Б» читается «из А в Б»):

А → Б
А → В
Б → Г
В → Г
В → К
Г → К

Расставляем числа:

N(А) = 1                  (старт)
N(Б) = N(А)        = 1    (входит только из А)
N(В) = N(А)        = 1    (входит только из А)
N(Г) = N(Б) + N(В) = 2    (входит из Б и из В)
N(К) = N(В) + N(Г) = 3    (входит из В и из Г)

Ответ — 3. Проверим перебором: А — Б — Г — К, А — В — Г — К, А — В — К. Ровно три маршрута. На схемах из 8–11 городов перебором пользоваться уже нельзя (ответы 12, 13, 14, 17 — и один-два маршрута обязательно потеряются), но на таком мини-примере он отлично показывает, почему метод верен.

Арифметика в задании 9 детская — ошибаются почти всегда на чтении рисунка. Лучшее доказательство — три задания из открытого банка ФИПИ, у которых одинаковый каркас: восемь городов (А, Б, В, Г, Д, Е, Ж, К), ровно 14 дорог в каждом, одинаковое расположение кружков на рисунке. Различаются они буквально одной-двумя стрелками — и ответы получаются разные.

Схема 1 — ответ 10

Дороги: А→Б, А→В, А→Г, А→Д, Б→В, Б→Е, В→Е, В→К,
        Д→Г, Г→К, Г→Ж, Д→Ж, Е→К, Ж→К

N(А) = 1
N(Б) = 1                       N(Д) = 1
N(В) = N(А) + N(Б) = 2
N(Г) = N(А) + N(Д) = 2
N(Е) = N(Б) + N(В) = 1 + 2 = 3
N(Ж) = N(Г) + N(Д) = 2 + 1 = 3
N(К) = N(В) + N(Г) + N(Е) + N(Ж) = 2 + 2 + 3 + 3 = 10

Схема 2 — ответ 13

Дороги: А→Б, А→В, А→Г, А→Д, Б→В, В→Е, В→Г, В→К,
        Д→Г, Г→К, Г→Ж, Д→Ж, Е→К, Ж→К

N(А) = 1
N(Б) = 1                       N(Д) = 1
N(В) = N(А) + N(Б) = 2
N(Г) = N(А) + N(В) + N(Д) = 1 + 2 + 1 = 4
N(Е) = N(В) = 2
N(Ж) = N(Г) + N(Д) = 4 + 1 = 5
N(К) = N(В) + N(Г) + N(Е) + N(Ж) = 2 + 4 + 2 + 5 = 13

Схема 3 — ответ 12

Дороги: А→Б, А→В, А→Г, А→Д, Б→В, Б→Е, В→Г, В→К,
        Д→Г, Г→К, Г→Ж, Д→Ж, Е→К, Ж→К

N(А) = 1
N(Б) = 1                       N(Д) = 1
N(В) = N(А) + N(Б) = 2
N(Г) = N(А) + N(В) + N(Д) = 1 + 2 + 1 = 4
N(Е) = N(Б) = 1
N(Ж) = N(Г) + N(Д) = 4 + 1 = 5
N(К) = N(В) + N(Г) + N(Е) + N(Ж) = 2 + 4 + 1 + 5 = 12

Вывод практический: сначала выпишите список дорог (столбиком, как выше), пересчитайте его длину и сверьте с рисунком, и только потом считайте. Особенно охотятся за вертикальной стрелкой внутри «столбца» (В → Г — её легко принять за элемент оформления) и за короткой стрелкой в верхнем ряду (Б → Е).

Если спрашивают «сколько путей из $A$ в $K$, проходящих через город $X$», складывать ничего не нужно — здесь работает умножение. Любой такой путь однозначно разрезается городом $X$ на два куска: «от $A$ до $X$» и «от $X$ до $K$». И наоборот: любой первый кусок можно склеить с любым вторым — получится допустимый путь. Значит:

• $N_{A \to X}$ считается обычной расстановкой чисел от старта: ставим 1 в $A$ и доходим до $X$.
• $N_{X \to K}$ считается второй, отдельной расстановкой: теперь стартом объявляем $X$, пишем в нём $1$, а все города, недостижимые из $X$, получают 0.
• Оба числа перемножаем. Ошибка «сложить вместо умножить» — одна из самых частых: $4 \cdot 3 = 12$, а не $4 + 3 = 7$.

Существует и второй приём — «вычеркнуть все дороги, которые минуют город $X$, и досчитать по обрезанной схеме». Он даёт тот же ответ, но требует аккуратности: легко вычеркнуть лишнее. Держите его как проверочный, а основным считайте произведение.

Тут два равноправных способа.

Способ 1 — вычеркнуть город

Стираем сам город $X$ вместе со всеми входящими и исходящими стрелками и заново расставляем числа по обрезанной схеме. Число в финише — ответ. Способ надёжный и наглядный: если путь не должен проходить через город, этот город просто не участвует в суммах.

Способ 2 — через дополнение

Все пути делятся ровно на два класса: те, что проходят через $X$, и те, что не проходят. Отсюда:

Способ 2 удобен, когда общее количество путей вы уже посчитали. И он же — идеальная перекрёстная проверка: посчитайте одним способом, проверьте другим. Если числа не сошлись, вы где-то потеряли стрелку.

В КИМ ОГЭ по информатике два «графовых» задания, и у них один и тот же код кодификатора — 2.11. Из-за этого их постоянно путают. Различайте по вопросу:

Простое правило: увидели километры — это задание 4, увидели стрелки — задание 9. В задании 9 весов нет вообще, и «самый короткий» маршрут ничем не лучше «самого длинного»: оба считаются одним путём каждый.

День 1–2: разберите метод на маленьких схемах (6–7 городов, ответы 6–9). Обязательно решайте двумя способами — расстановкой чисел и полным перебором маршрутов — и сверяйте: так приём становится не «магией», а понятным правилом. День 3–5: перейдите на схемы из 8 городов, но сохраняйте привычку сначала выписывать список дорог столбиком и пересчитывать его длину. День 6–7: возьмите три «схемы-близнеца» из этой статьи, закройте ответы и решите заново — это лучший тест на внимательность к рисунку.

День 1–3: отработайте подтип «проходящих через город X» — правило произведения с обязательной второй расстановкой от X, и подтип «не проходящих через X» двумя способами (вычёркивание и вычитание из общего). Каждую задачу проверяйте вторым способом, пока результаты не начнут сходиться с первого раза. День 4–5: работайте на время — не больше 4 минут на задание, включая выписывание дорог. День 6–7: прорешайте задания 4 и 9 вперемешку, чтобы окончательно развести в голове «километры» и «количество путей», и проверьте себя в тренажёре на заданиях из банка ФИПИ.