Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача Задача №3829591
А
Аноним
7 часов назад · публичный вопрос
А
Аноним

В городе построена сеть односторонних дорог между перекрёстками (вершины графа). Нужно определить, сколькими различными путями можно добраться из пункта L1 в пункт L2

Запрос пользователя

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

Ответ нейросети
7 часов назад

Краткий ответ: 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 \]

Проверка перебором путей:

  1. L1 → B → C → F → L2
  2. L1 → B → C → G → L2
  3. L1 → B → E → F → L2
  4. L1 → D → C → F → L2
  5. L1 → D → C → G → L2
  6. L1 → D → I → G → L2

Всего действительно 6 путей.