Сверь числа и знаки с фото.
В городе построена сеть односторонних дорог между перекрёстками (вершины графа). Нужно определить, сколькими различными путями можно добраться из пункта L1 в пункт L2, не заезжая дважды на один и тот же перекрёсток. [Рисунок: ориентированный граф с вершинами L1, B, D, C, E, F, G, I, L2; видны стрелки L1→B, L1→D, B→E, B→C, D→C, D→I, C→F, C→G, E→F, I→G, F→L2, G→L2.] [Таблица: строки L1, B, C, D, E, F, G, I, L2; столбцы «Шаг 1», «Шаг 2», «Шаг 3», «Шаг 4», «Шаг 5».] Результат: ___
Краткий ответ: 6 различных путей. В поле «Результат» нужно вписать 6.
Считаем число путей до каждой вершины: сколько путей в неё входит, столько и суммируем.
\[ N(\text{L1})=1 \]
\[ N(B)=1,\quad N(D)=1 \]
\[ N(C)=N(B)+N(D)=1+1=2 \]
\[ N(E)=N(B)=1,\quad N(I)=N(D)=1 \]
\[ N(F)=N(C)+N(E)=2+1=3 \]
\[ N(G)=N(C)+N(I)=2+1=3 \]
\[ N(\text{L2})=N(F)+N(G)=3+3=6 \]
Проверка перебором путей:
- L1 → B → C → F → L2
- L1 → B → C → G → L2
- L1 → B → E → F → L2
- L1 → D → C → F → L2
- L1 → D → C → G → L2
- L1 → D → I → G → L2
Всего действительно 6 путей.