Пути в графе: три правила

Для ориентированного графа без циклов. Двигайтесь только по стрелкам.

A = 1 → B = 1 → C = 1 + 1 = 2 → D = 1 + 2 = 3.

1. Все пути: складывайте входящие

У старта поставьте 1. У следующей вершины — сумму чисел у всех её предшественников. Обрабатывайте вершину после всех, кто ведёт в неё.

Из A в D три пути: A–B–D, A–C–D, A–B–C–D.

2. Через вершину: умножайте участки

Через B: число путей A → B умножить на число путей B → D. В примере: 1 × 2 = 2.

3. Без вершины: исключите её

Уберите B с прилегающими стрелками и пересчитайте. Остаётся A–C–D: 1 путь. Проверка: все пути − пути через B = 3 − 2 = 1.

Проверьте себя

1. Сколько путей из A в D проходит через C?
2. Сколько путей из A в D не проходит через C?

Ответы: 1) 2 — A–C–D и A–B–C–D; 2) 1 — A–B–D.

Не путайте количество путей с числом стрелок или длиной маршрута. Пересечение линий без обозначенной вершины не создаёт новый переход.