Задание 9: Анализирование информации, представленной в виде схем

Типичная формулировка: «На рисунке — схема дорог, связывающих города А, Б, В, ... По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К (Л)?»

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

• Граф — совокупность вершин (городов) и рёбер (дорог) между ними.
• Ориентированный граф — граф, в котором рёбра имеют направление (можно двигаться только по стрелке, в обратную сторону — нельзя).
• Путь из вершины $A$ в вершину $B$ — последовательность рёбер, ведущая от $A$ к $B$ по направлению стрелок, без повторения вершин (циклы в схемах ОГЭ обычно не встречаются).
• Правило суммы: если в вершину $X$ можно попасть только из вершин $P_1, P_2, \dots, P_k$, то количество путей до $X$ из начальной точки равно сумме количеств путей до каждой из этих вершин: $$N(X) = N(P_1) + N(P_2) + \dots + N(P_k)$$
• Начальной вершине присваивается значение $N(A) = 1$ (существует ровно один "путь" — остаться на месте / начать движение).
• Если в вершину нет входящих рёбер (кроме старта), она недостижима, и $N = 0$.
• Вершины нужно обрабатывать в порядке топологической сортировки — то есть только после того, как посчитаны значения для всех вершин, из которых в неё ведут стрелки.
• Для подсчёта путей, проходящих через определённый пункт $C$, используется умножение: число путей из $A$ в $B$ через $C$ равно произведению числа путей из $A$ в $C$ и числа путей из $C$ в $B$: $$N(A \to B \text{ через } C) = N(A \to C) \cdot N(C \to B)$$
• Число путей, не проходящих через $C$, находится как разность общего числа путей и числа путей, проходящих через $C$: $$N(A \to B \text{ мимо } C) = N(A \to B) - N(A \to B \text{ через } C)$$

1. Внимательно рассмотреть схему, выписать все вершины (города) и все рёбра со стрелками направления.
2. Определить стартовую и конечную вершину задачи.
3. Присвоить стартовой вершине число путей, равное 1.
4. Определить порядок обработки остальных вершин: вершина обрабатывается только тогда, когда обработаны все вершины, из которых в неё есть стрелка (топологический порядок, обычно совпадает с порядком "слева направо" на схеме).
5. Для каждой вершины найти все входящие в неё стрелки, определить вершины-источники, сложить их значения — это и есть число путей до текущей вершины.
6. Дойти до конечной вершины и записать итоговое число — это ответ на вопрос "сколько всего путей". …