На рисунке - схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Question

Реши задание на изображении

Расшифровка фото нейросетью:
На рисунке - схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из A в К, не проходящих через В?
[Рисунок: ориентированный граф с вершинами A, Б, В, Г, Д, Е, Ж, З, И, К.]

На рисунке - схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из A в И, проходящих через Г?
[Рисунок: ориентированный граф с вершинами A, Б, В, Г, Д, Е, Ж, З, И.]

На рисунке представлена схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из A в М, проходящих через Ж, но не проходящих через Д?
[Рисунок: ориентированный граф с вершинами A, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.]

На рисунке представлена схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из A в Т, проходящих через К, но не проходящих через В?
[Рисунок: ориентированный граф с вершинами A, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, Т.]

Answer

На фото четыре отдельные однотипные задачи — решил их сверху вниз.

Ответы:

1. $14$

2. $12$

3. $27$

4. $64$

Как считать. Для ориентированного графа без циклов число путей в вершину равно сумме чисел путей из всех вершин, откуда в неё ведёт стрелка. Если путь обязан проходить через вершину $X$, считаем отдельно $A\to X$ и $X\to$ цель, а результаты перемножаем. Если через вершину проходить нельзя, её и её дороги исключаем.

Краткие подсчёты:

1. Убираем $В$. По схеме:
$$
A=1,\quad Б=1,\quad Д=1,\quad Г=2,\quad З=2,\quad Ж=4,\quad Е=5,\quad И=3,
$$
$$
K=5+4+2+3=14.
$$

2. Путей из $A$ в $Г$: $4$. От $Г$ до $И$: $3$ пути. Значит:
$$
4\cdot 3=12.
$$

3. Без прохода через $Д$: путей $A\to Ж$ — $9$. От $Ж$ до $М$ — $3$ пути. Значит:
$$
9\cdot 3=27.
$$

4. Без прохода через $В$: путей $A\to K$ — $8$. От $K$ до $T$ — $8$ путей. Значит:
$$
8\cdot 8=64.
$$