№ 23. Графы: количество путей (новое в проекте 2027)

Главное

В ориентированном графе без циклов число путей из A в вершину X равно сумме путей во все вершины, из которых есть дуга в X. Считаем вершины по порядку от начала к концу.

Правила

1. Путей в X = сумма путей в предшественников
2. Считаем в топологическом порядке
3. Через обязательную вершину — произведение частей

Разберём пример

Дуги: A→B, A→C, B→D, C→D, B→C. Сколько путей из A в D?

3: в B — 1, в C — 1 + 1 = 2, в D — 1 + 2 = 3

Частые ошибки

• Считать вершину раньше, чем посчитаны все её предшественники.

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.