Главная идея

Число путей в вершину — сумма чисел путей в её соседей

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

N(старт) = 1 N(X) = N(Y₁) + N(Y₂) + … через X: N₁ · N₂
01

Путь и его длина

Путь А→Б→В состоит из двух рёбер: длина 2. Путь А→В из одного ребра имеет длину 1. Пути различны, если различны последовательности вершин. Число рёбер графа и число путей — разные величины.

02

Умножить или сложить

Части одного маршрута идут друг за другом: числа способов умножают (3 дороги и затем 2 дороги — 6 способов). Разные маршруты исключают друг друга: числа способов складывают (4 и 3 — 7 способов).

03

Метод подписей

Последний шаг пути в X — одна из входящих стрелок. Если она идёт из Y, до Y можно дойти N(Y) способами. Разные стрелки дают разные пути, поэтому подписи складываются. Подписывай вершины по порядку: сначала те, из которых идут стрелки в неё.

04

Через вершину и неориентированный граф

Через X проходят N₁·N₂ путей (до X и после X). Не через X: все пути минус эти. В неориентированном графе подписи не работают: можно ходить по кругу, поэтому вершины не повторяют, а пути выписывают перебором.

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

Подпиши вершины числом путей из старта

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

Четыре разобранные задачи

Изучено: 0/4

Сначала попробуй решить задачу сам. Затем открывай шаги разбора по одному и сравнивай свой ход мысли.

Проверка перечислением

Выпиши все пути и сравни с подписями

  1. 1

    Нарисуй граф по списку рёбер

    Расставь вершины слева направо, стрелки по списку. Так проще заметить входящие стрелки.

  2. 2

    Подпиши вершины по порядку

    N(старт) = 1. Для остальных сложи подписи вершин, из которых идут стрелки в неё.

  3. 3

    Проверь перечислением

    Выпиши все пути из старта в финиш: от каждой вершины иди по всем стрелкам. Число путей должно совпасть с подписью финиша.

  4. 4

    Учти условие

    Через вершину X: N(до X) · N(от X). Не через X: все пути минус пути через X. В неориентированном графе вершины не повторяют.

Задача и все её пути

Твоё решение

Самостоятельная работа

Двадцать задач с проверкой и разбором

Верно: 0/20

Ответ — одно число. После первой проверки открывается полный разбор задачи.