В9 — Количество путей в графе

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

Принцип (он один для всех пяти задач)

• Пусть \(N(X)\) — число путей из А в вершину \(X\). Тогда \(N(X)=\sum N(Y)\) по всем вершинам \(Y\), из которых в \(X\) идёт стрелка, причём \(N(A)=1\).
• Считай вершины по порядку «слева направо», чтобы к каждой уже были готовы все её предшественники.
• Пути, проходящие через промежуточный город (Г, В или C), считаются так: \[N_{\text{через }Г}=N(Г)\cdot M(Г\to K),\] где \(M(Г\to K)\) — число путей из Г в К, найденное тем же способом, но стартуя из Г.
• Проверка: \(N_{\text{через }Г}\) не может быть больше общего числа путей из А в К.

Что нужно от тебя Пришли крупный скриншот нужной схемы — например, №1 — и я сразу посчитаю все вершины по порядку. Если нужны все пять, лучше по одной: на этом снимке направления стрелок неразличимы.