Задание 9. Как посчитать пути в графе
На рисунке показаны города и дороги со стрелками. Нужно узнать, сколькими разными маршрутами можно добраться из одного города в другой. Начнём с маленькой схемы, разберём несколько способов, а затем решим экзаменационный пример.
1. Как читать схему
Город — вершина
Кружок с буквой обозначает город. В теории графов такой объект называют вершиной.
Стрелка — направление дороги
Стрелка A → B разрешает движение из A в B. Для поездки обратно нужна отдельная стрелка B → A.
Путь — целый маршрут
Путь — последовательность городов, в которой каждый переход разрешён стрелкой. Например: A → B → D.
По этой схеме можно попасть из A в D несколькими способами.
| Маршрут |
Можно ли так проехать? |
| A → B → D |
Да: обе стрелки есть. |
| A → C → D |
Да: обе стрелки есть. |
| A → B → C → D |
Да: есть вертикальная стрелка B → C. |
| A → C → B → D |
Нет: стрелки C → B нет. |
Считаем полные пути от старта до финиша. Количество дорог и количество путей — разные величины. На этой схеме 5 дорог, но всего 3 пути из A в D.
Если линии на рисунке пересекаются, но в месте пересечения не обозначен город, переходить с одной дороги на другую нельзя. Длина нарисованной стрелки также не влияет на число путей.
Во всех схемах этого разбора нельзя по стрелкам вернуться в уже пройденный город. Такие графы называют графами без циклов. Это позволяет считать пути по очереди, используя уже найденные значения.
2. Главный способ: считаем от старта
Пусть N(X) — количество разных путей от начального города A до города X. Возле каждой вершины будем записывать именно это число.
В начале ставим 1
Записываем N(A) = 1: есть один способ оказаться в начале маршрута — уже находиться в A, ещё не проехав ни одной дороги.
Это начальное значение позволяет правильно посчитать пути в соседние города.
В остальных городах складываем
Смотрим, откуда стрелки входят в рассматриваемый город. Складываем числа у этих предыдущих городов.
Если попасть в город из A невозможно, его значение равно 0.
Правило: число путей в город равно сумме чисел у всех городов, из которых в него ведёт дорога.
| Город |
Откуда можно приехать одним переходом |
Как считаем |
| A |
Начало маршрута |
N(A) = 1 |
| B |
Из A |
N(B) = 1 |
| C |
Из A и B |
N(C) = 1 + 1 = 2 |
| D |
Из B и C |
N(D) = 1 + 2 = 3 |
Буква в кружке — город. Рукописное число рядом — количество путей из A в этот город.
Почему в D складываем 1 и 2?
Последняя дорога любого пути в D — либо B → D, либо C → D.
Через последнюю дорогу B → D приходит один путь: A → B → D.
Через последнюю дорогу C → D приходят два пути: A → C → D и A → B → C → D.
Эти группы не пересекаются: у одного маршрута не может быть двух разных последних дорог. Поэтому 1 + 2 = 3.
Две входящие стрелки не обязательно означают два пути. По одной последней дороге могут прийти разные маршруты, которые различались раньше.
3. Другой способ: выписать все маршруты от старта
Начинаем каждый маршрут в A
Последовательно перебираем разрешённые продолжения:
A → B → D
A → B → C → D
A → C → D
Получили 3 пути. Этот способ удобно использовать на маленькой схеме или для проверки ответа.
На большой схеме легко забыть маршрут или записать его дважды, поэтому полезнее подписывать количества у городов.
Оба способа начинаются в A. В первом мы накапливаем количества у городов, во втором — выписываем каждый маршрут целиком.
4. В каком порядке подписывать числа
Город можно обработать, когда уже известны числа у всех его предшественников — городов, из которых в него входят стрелки.
1. Найти начало
Ставим у начального города 1. Проверяем, в какой город требуется прийти.
2. Выбрать готовый город
Находим город, для которого уже посчитаны все входящие ветви. Смотрим на стрелки, включая вертикальные и наклонные.
3. Сложить и записать
Складываем числа у предшественников. Результат подписываем возле выбранного города.
4. Дойти до финиша
Повторяем действия. Число у конечного города — ответ, если в условии нет дополнительных ограничений.
Часто удобный порядок идёт слева направо, но это лишь особенность рисунка. Порядок задают стрелки, а не алфавит и не положение букв. Если один предшественник ещё не посчитан, вернёмся к нему сначала.
5. Экзаменационный пример: из A в H
Разберём схему из задания 9 проекта демоверсии ОГЭ 2026, опубликованного ФИПИ. Рисунок перерисован; все дороги и их направления сохранены.
Условие
Между городами A, B, C, D, E, F, G, H проложены односторонние дороги. Их направления показаны стрелками. Определите, сколько разных маршрутов ведёт из A в H.
| Фраза условия |
Что нужно сделать |
| «Из A» |
Начать подсчёт в A и поставить там 1. |
| «В H» |
Найти число у H. Маршрут, закончившийся раньше, ещё не является ответом. |
| «Односторонние дороги» |
Каждый переход проверять по направлению стрелки. |
| «Разных маршрутов» |
Посчитать все допустимые последовательности городов, включая длинные. |
Сначала проверим, что правильно прочитали рисунок. Ниже перечислены все дороги:
| Откуда |
Куда ведут стрелки |
| A |
B, C, D |
| B |
E |
| C |
E, F |
| D |
F |
| E |
F, G |
| F |
G, H |
| G |
H |
| H |
Дальше дорог нет |
Обрати внимание: между E и F стрелка направлена E → F, а между F и G — F → G. Поэтому сначала считаем E, затем F, затем G.
Способ 1. Подсчёт от A
| Город |
Входящие дороги |
Количество путей из A |
| A |
Старт |
1 |
| B |
A → B |
1 |
| C |
A → C |
1 |
| D |
A → D |
1 |
| E |
B → E; C → E |
1 + 1 = 2 |
| F |
C → F; D → F; E → F |
1 + 1 + 2 = 4 |
| G |
E → G; F → G |
2 + 4 = 6 |
| H |
F → H; G → H |
4 + 6 = 10 |
У каждой вершины — количество путей из A. У H получилось 10.
Почему в F не 3, хотя входящих дорог три? До E уже есть два маршрута: A → B → E и A → C → E. Каждый можно продолжить дорогой E → F. Вместе с маршрутами A → C → F и A → D → F получаем четыре.
Почему в H складываем 4 и 6? Один маршрут заканчивается дорогой F → H, другой — G → H. Даже если путь через G раньше прошёл через F, это другой маршрут, поэтому двойного счёта здесь нет.
Способ 2. Полный перебор по первому шагу
Разделим маршруты на три группы по первой дороге. У каждой группы свой первый шаг, поэтому группы не пересекаются:
| Первый шаг |
Все маршруты в этой группе |
Сколько |
| A → B |
A → B → E → F → G → H
A → B → E → F → H
A → B → E → G → H |
3 |
| A → C |
A → C → E → F → G → H
A → C → E → F → H
A → C → E → G → H
A → C → F → G → H
A → C → F → H |
5 |
| A → D |
A → D → F → G → H
A → D → F → H |
2 |
3 + 5 + 2 = 10.
Полный список удобно использовать как проверку. При большом числе маршрутов достаточно чисел у вершин.
Ответ: 10. В бланке записываем только число.
6. Если путь должен пройти через определённый город
Изменим условие предыдущего примера: сколько путей из A в H проходят через F?
Сначала дойти до F
Количество путей из A в F уже известно: 4.
A → B → E → F
A → C → E → F
A → C → F
A → D → F
Затем дойти от F до H
Считаем новый участок от его начала — города F. В F ставим 1. Из F в G ведёт одна дорога, поэтому у G тоже 1. В H входят дороги из F и G:
F: 1; G: 1; H: 1 + 1 = 2.
Получаются два продолжения:
F → H
F → G → H
Каждый из четырёх способов дойти до F сочетается с каждым из двух продолжений. Поэтому здесь умножаем:
4 · 2 = 8 путей.
| До обязательного города |
Продолжение 1 |
Продолжение 2 |
| A → B → E → F |
A → B → E → F → H |
A → B → E → F → G → H |
| A → C → E → F |
A → C → E → F → H |
A → C → E → F → G → H |
| A → C → F |
A → C → F → H |
A → C → F → G → H |
| A → D → F |
A → D → F → H |
A → D → F → G → H |
Правило для обязательного города X:
число путей через X = число путей от старта до X · число путей от X до финиша.
В графе без циклов такой маршрут однозначно разбивается на две части.
Если хотя бы одна часть невозможна, один из множителей равен нулю и подходящих путей нет. При соединении частей общий город пишем один раз.
7. Если через город проходить нельзя
Теперь найдём пути из A в H, не проходящие через F. Есть два удобных способа.
Способ 1. Зачеркнуть запрещённые дороги
Отметим город F и все входящие и исходящие дороги красными волнистыми линиями. Зачёркнутыми дорогами пользоваться нельзя. Снова начинаем подсчёт в A и учитываем только незачёркнутые стрелки.
Исходный граф виден целиком. Красные зачёркивания отмечают город F и дороги, которые нельзя использовать.
В E получаем 1 + 1 = 2. В G учитываем только дорогу E → G, поэтому у G стоит 2. В H учитываем только G → H и получаем 2. У запрещённого города F число не подписываем.
Два оставшихся маршрута:
A → B → E → G → H
A → C → E → G → H
Город D достижим из A, но дорога D → F зачёркнута. Продолжить этот маршрут до H нельзя, поэтому ветка через D не добавляет путей к ответу.
Способ 2. Вычесть неподходящие пути
Всего путей из A в H — 10. Из них проходят через F — 8. Остальные F не посещают:
10 − 8 = 2.
Каждый путь либо проходит через F, либо не проходит. Эти две группы не пересекаются и вместе дают все маршруты.
Нельзя просто вычесть 4. Четыре — это число способов дойти до F. Нам нужно убрать полные маршруты до H, проходящие через F: их 4 · 2 = 8.
8. Несколько условий: как не запутаться
Следующие примеры используют тот же граф из A в H. Это расширение основного способа.
Пройти и через E, и через F
По направлениям стрелок сначала идёт E, затем F. Разбиваем маршрут на три части: A → E, E → F, F → H.
2 · 1 · 2 = 4.
Между E и F здесь только один подходящий путь — прямая дорога E → F. Через G попасть обратно в F нельзя.
Пройти через F, но не через E
Сначала зачёркиваем E и связанные с ним дороги. Теперь дойти до F можно только двумя способами: A → C → F и A → D → F.
Из F до H по-прежнему два продолжения.
2 · 2 = 4.
Обязательно проехать по дороге C → F
До начала этой дороги, города C, есть один путь. По самой дороге проезжаем одним способом. После неё из F до H — два продолжения.
1 · 1 · 2 = 2.
Получаем A → C → F → H и A → C → F → G → H.
Пройти через E или через F
На участке от E до H начинаем подсчёт в E: у E — 1, у F — 1, у G — 1 + 1 = 2, у H — 1 + 2 = 3.
Через E проходит 2 · 3 = 6 путей, через F — 4 · 2 = 8. Но 4 пути посещают оба города и попадают в обе группы.
6 + 8 − 4 = 10.
Здесь работает та же идея, что в задании 8: для объединения убираем двойной счёт общей части.
| Что делаем |
Какое действие нужно |
Почему |
| Объединяем пути с разными последними дорогами |
Сложение |
Эти варианты не могут совпасть. |
| Соединяем части маршрута через обязательный город |
Умножение |
Каждое начало сочетается с каждым продолжением. |
| Убираем пути через запрещённый город |
Вычитание |
Из всех полных маршрутов убираем неподходящие. |
| Объединяем условия «через E» и «через F» |
Сложение с вычитанием общей части |
Некоторые пути выполняют оба условия. |
9. Частые ошибки и проверка ответа
- Считать дороги вместо путей. Одна последняя дорога может завершать несколько разных маршрутов.
- Не заметить вертикальную стрелку. В экзаменационном примере пропуск E → F изменит числа у F, G и H.
- Считать строго по алфавиту. Сначала должны быть готовы все предшественники текущего города.
- Поставить в начале 0. Начальное значение равно 1; иначе пути не начнут накапливаться.
- Сложить числа у всех городов. Ответ находится только у финиша; остальные числа — промежуточные результаты.
- Использовать старые числа для нового участка. На участке от F до H начинаем новый подсчёт и ставим в F число 1.
- При обязательном городе сложить части. Нужно перемножить число начал и продолжений.
- После запрета города оставить старые числа ниже по графу. Их нужно пересчитать, пропуская зачёркнутые дороги.
Как проверить себя: ещё раз пройти по стрелкам от старта; на маленьком графе выписать все маршруты; проверить, что «через X» + «без X» = «все пути». В нашем примере 8 + 2 = 10.
Число путей через обязательный город или по обязательной дороге не может превышать общее число путей. Запрет города или дороги также не может увеличить число допустимых маршрутов.
10. Проверь себя на новой схеме
Для всех шести вопросов используем один и тот же граф. Во всех случаях начало — A, конец — E. Сначала реши самостоятельно, затем открой ответ.
Дороги для проверки рисунка: A → B, A → C, B → C, B → D, C → D, C → E, D → E.
1. Все пути
Сколько всего путей ведёт из A в E?
Проверить ответ и решение
Ответ: 5.
A: 1; B: 1; C: 1 + 1 = 2;
D: 1 + 2 = 3;
E: 2 + 3 = 5.
Проверка: A → B → D → E; A → B → C → D → E; A → B → C → E; A → C → D → E; A → C → E.
2. Через C
Сколько путей проходит через город C?
Проверить ответ и решение
Ответ: 4.
До C есть 2 пути. Из C в E есть 2 продолжения: C → E и C → D → E.
2 · 2 = 4.
3. Без C
Сколько путей не проходит через город C?
Проверить ответ и решение
Ответ: 1.
5 − 4 = 1.
Остаётся только A → B → D → E.
4. Через B и D
Сколько путей проходит и через B, и через D?
Проверить ответ и решение
Ответ: 2.
До B — 1 способ. Из B в D — 2: напрямую или через C. Из D в E — 1.
1 · 2 · 1 = 2.
Маршруты: A → B → D → E и A → B → C → D → E.
5. Через C, но без B
Сколько путей проходит через C, но не проходит через B?
Проверить ответ и решение
Ответ: 2.
Зачёркиваем B и связанные с ним дороги. До C остаётся один путь A → C. После C возможны два продолжения.
1 · 2 = 2.
Маршруты: A → C → E и A → C → D → E.
6. По дороге B → C
Сколько путей обязательно использует дорогу B → C?
Проверить ответ и решение
Ответ: 2.
До B — 1 путь. После дороги B → C остаётся 2 продолжения из C в E.
1 · 1 · 2 = 2.
Маршруты: A → B → C → E и A → B → C → D → E.
Источник экзаменационной схемы: ФИПИ, проект демонстрационного варианта ОГЭ 2026 по информатике, задание 9. Условие изложено своими словами; направления дорог сохранены. Остальные схемы, упражнения и пояснения подготовлены для этого разбора.