Количество путей в графе: как считать по схеме дорог

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

На странице

Теория
Решённые примеры: 4
Типичные ошибки
Где встречается на экзамене
Вопросы и ответы

Теория

Что нарисовано на схеме

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

Правило суммы

У начального города поставь 1. У каждого следующего города число равно сумме чисел тех городов, из которых в него ведут стрелки. Число у конечного города — ответ.

Почему это верно: в город можно приехать только по одной из входящих дорог. Если в город X ведут дороги из B и из C, то каждый путь в X — это путь в B или путь в C, продолженный одной дорогой. Поэтому путей в X столько, сколько путей в B и в C вместе.

В каком порядке считать

Число у города можно ставить, только когда подписаны все города, из которых в него приходят стрелки. Иди по схеме от начала по стрелкам; если у города подписаны не все «входящие» города, отложи его и вернись позже. Перед сложением пересчитай стрелки, которые входят в город, — слагаемых должно быть столько же.

Пути через заданный город

Путь через город X состоит из двух частей: от начала до X и от X до конца. Любое начало можно продолжить любым концом, поэтому числа перемножают: пути от начала до X умножают на пути от X до конца. Вторую часть считают заново, поставив 1 у города X.

Пути мимо заданного города

Мысленно сотри запретный город вместе со всеми его дорогами и посчитай пути по оставшейся схеме. Город, в который теперь не попасть, получает 0. Второй способ: из числа всех путей вычесть число путей через этот город.

Отсюда проверка: все пути = пути через город + пути мимо города. В примерах ниже три задачи решены на одной схеме: 8 = 6 + 2.

Решённые примеры

Примеры взяты из тренажёра: там такие же задания, только числа и слова каждый раз новые.

1. Сколько путей из города в город

Форма демоверсии 2027 года: подписываем числа у городов по правилу суммы.

На схеме показаны дороги между городами A, B, C, D, E, F, G. Ехать по дороге можно только в ту сторону, куда показывает стрелка. Сколько существует различных путей из города A в город G?

Решение

Подписывай у каждого города, сколькими путями в него можно приехать из A. У самого A ставим 1, у каждого следующего города — сумму чисел тех городов, из которых в него ведут стрелки.
Иди по схеме слева направо — так, чтобы к моменту подсчёта все нужные слагаемые уже были известны: B = A = 1; C = A + B = 1 + 1 = 2; E = B + C = 1 + 2 = 3; D = E = 3; F = C = 2.
Последним считаем город G: G = D + E + F = 3 + 3 + 2 = 8. Путей из A в G — 8

Ответ: 8

Можно иначе. Считай с конца: у каждого города подпиши, сколькими путями из него можно доехать до G. У самого G ставим 1, у остальных — сумму чисел тех городов, в которые из него ведут стрелки: F = G = 1; D = G = 1; E = D + G = 1 + 1 = 2; C = E + F = 2 + 1 = 3; B = C + E = 3 + 2 = 5; A = B + C = 5 + 3 = 8. Число у города A — ответ: 8.

Если получилось другое число

10 — Столько на схеме дорог. А путь — это целый маршрут из A в G, он складывается из нескольких дорог.
3 — В город G ведут 3 дороги: из городов D, E, F. Сложи числа у всех этих городов.
7 — Это число городов на схеме. Нужно посчитать маршруты из A в G.

Решать такие же в тренажёре →

2. Пути через заданный город

Та же схема. Считаем две части пути отдельно и перемножаем.

Решение

Путь через C состоит из двух частей: из A в C и из C в G. Любое начало можно продолжить любым концом, поэтому число путей — это произведение.
Сколько путей из A в C. У A ставим 1, у каждого следующего города — сумму чисел тех городов, из которых в него ведут стрелки. Считаем только города, из которых можно доехать до C: B = A = 1; C = A + B = 1 + 1 = 2. В C ведут 2 пути.
Сколько путей из C в G. Начни счёт заново: у C ставим 1 и считаем только города, в которые из C можно попасть: E = C = 1; D = E = 1; F = C = 1; G = D + E + F = 1 + 1 + 1 = 3. Из C в G — 3 пути.
Перемножь: 2 · 3 = 6

Ответ: 6

Можно иначе. Посчитай все пути из A в G — их 8. Потом мысленно сотри город C вместе с его дорогами и посчитай снова: мимо C идут 2 пути. Остальные проходят через C: 8 − 2 = 6.

Если получилось другое число

8 — Это все пути из A в G. Среди них есть такие, которые обходят город C, — их считать не нужно.
5 — Числа путей до города C и после него нужно перемножить, а не сложить: каждое начало сочетается с каждым концом.
2 — Это пути из A в C. Из C ещё нужно доехать до G, и сделать это можно не одним способом.

Решать такие же в тренажёре →

3. Пути мимо заданного города

Та же схема без одного города. Вместе с предыдущим примером получается число всех путей.

Решение

Через город C ехать нельзя — мысленно сотри его вместе со всеми дорогами, которые в него входят и из него выходят.
На оставшейся схеме подписывай у каждого города, сколькими путями в него можно приехать из A. У A ставим 1, у каждого следующего города — сумму чисел тех городов, из которых в него ведут стрелки: B = A = 1; E = B = 1; D = E = 1; F = 0 (сюда теперь не попасть).
Последним считаем город G: G = D + E + F = 1 + 1 + 0 = 2. Путей мимо C — 2

Ответ: 2

Можно иначе. Посчитай все пути из A в G — их 8. Теперь пути через C: из A в C ведут 2 пути, из C в G — 3, всего 2 · 3 = 6. Остальные обходят C: 8 − 6 = 2.

Если получилось другое число

8 — Это все пути из A в G. Часть из них проходит через город C — их нужно убрать.
6 — Это, наоборот, пути, которые проходят через C. Спрашивают про те, что его обходят.

Решать такие же в тренажёре →

4. Схема из восьми городов

Городов больше, правило то же: важно не пропустить ни одной входящей стрелки.

На схеме показаны дороги между городами A, B, C, D, E, F, G, H. Ехать по дороге можно только в ту сторону, куда показывает стрелка. Сколько существует различных путей из города A в город H?

Решение

Подписывай у каждого города, сколькими путями в него можно приехать из A. У самого A ставим 1, у каждого следующего города — сумму чисел тех городов, из которых в него ведут стрелки.
Иди по схеме слева направо — так, чтобы к моменту подсчёта все нужные слагаемые уже были известны: B = A = 1; C = A + B = 1 + 1 = 2; D = B = 1; E = C + D = 2 + 1 = 3; G = E = 3; F = D + G = 1 + 3 = 4.
Последним считаем город H: H = F + G = 4 + 3 = 7. Путей из A в H — 7

Ответ: 7

Можно иначе. Считай с конца: у каждого города подпиши, сколькими путями из него можно доехать до H. У самого H ставим 1, у остальных — сумму чисел тех городов, в которые из него ведут стрелки: F = H = 1; G = F + H = 1 + 1 = 2; E = G = 2; D = E + F = 2 + 1 = 3; C = E = 2; B = C + D = 2 + 3 = 5; A = B + C = 5 + 2 = 7. Число у города A — ответ: 7.

Если получилось другое число

11 — Столько на схеме дорог. А путь — это целый маршрут из A в H, он складывается из нескольких дорог.
4 — В город H ведут 2 дороги: из городов F, G. Сложи числа у всех этих городов.
8 — Это число городов на схеме. Нужно посчитать маршруты из A в H.

Решать такие же в тренажёре →

Типичные ошибки

Считают дороги, а не пути.
Пропускают одну из входящих стрелок и складывают не все числа.
Ставят число у города раньше, чем подписаны все города перед ним.
Складывают числа городов, в которые ведут стрелки из данного города, а не тех, из которых стрелки приходят.
В задаче «через город» складывают две части вместо того, чтобы перемножить.
В задаче «мимо города» стирают город, но оставляют его дороги.

Где встречается на экзамене

Задание 9 — число путей по схеме дорог со стрелками.
Задание 4 — тоже граф, но заданный таблицей: ищут кратчайший путь.

Решать задания на число путей Пути через городБесплатно, без регистрации: каждый раз новое задание и разбор ошибки.

Вопросы и ответы

Как посчитать количество путей в графе?

У начального города поставить 1, у каждого следующего — сумму чисел городов, из которых в него ведут стрелки. Число у конечного города — количество путей.

Как найти число путей, проходящих через город?

Число путей от начала до этого города умножить на число путей от него до конца.

Как найти число путей, не проходящих через город?

Убрать город и его дороги со схемы и посчитать пути заново. Или из всех путей вычесть те, что проходят через город.

Почему числа складывают, а не перемножают?

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

Соседние темы

Узнай, какие задания уже получаютсяКороткая диагностика по первой части занимает пять минут. После неё — план на каждый день до экзамена.

Пройти диагностику

Теория — школьная программа 7–9 классов; задания составлены нами, числа и слова в тренажёре каждый раз новые. Факты об экзамене — из демоверсии, спецификации и кодификатора ФИПИ для ОГЭ 2027 года; на день обновления документы опубликованы как проект. Обновлено 11.10.2026.