ОГЭ по информатике (9 задание) На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, не проходящих через пункт Е?

Привет! Давай разберем эту задачку по графам.

Что от нас хотят? Найти количество путей из точки А в точку Л, но с одним важным условием — НЕ заходить в точку Е. Картинку с дорогой мы видим, стрелочки показывают направление движения. Это значит, что мы можем идти только туда, куда указывает стрелка.

Как будем решать? Мы будем считать пути от каждой точки до следующей, двигаясь от начала (А) к концу (Л). Так как нам нельзя в Е, мы просто будем игнорировать все пути, которые туда ведут.

Поехали считать:

1. Из А:
   
   • В Б: 1 путь
   • В Г: 1 путь
   • В В: 1 путь
2. Из Б:
   
   • В Г: 1 путь (Итого из А через Б в Г: 1 путь)
3. Из В:
   
   • В Г: 1 путь (Итого из А через В в Г: 1 путь)
   • В И: 1 путь (Итого из А через В в И: 1 путь)
4. Из Г:
   
   • В Д: 1 путь (Итого из А через Б в Г в Д: 1 путь; Итого из А через В в Г в Д: 1 путь. Всего в Д через Г: 2 пути)
   • В Е: 1 путь (Внимание! Этот путь нам не подходит, так как мы не можем заходить в Е.)
   • В Ж: 1 путь (Итого из А через Б в Г в Ж: 1 путь; Итого из А через В в Г в Ж: 1 путь. Всего в Ж через Г: 2 пути)
   • В И: 1 путь (Итого из А через Б в Г в И: 1 путь; Итого из А через В в Г в И: 1 путь. Всего в И через Г: 2 пути)
5. Из Д:
   
   • В Ж: 1 путь (Итого в Ж через Д: 2 пути)
   • В К: 1 путь (Итого в К через Д: 2 пути)
6. Из Ж:
   
   • В Л: 1 путь (Итого в Л через Ж: 2 пути)
7. Из И:
   
   • В К: 1 путь (Итого в К через И: 1 путь)
8. Из К:
   
   • В Л: 1 путь (Итого в Л через К: 2 + 1 = 3 пути)

Сложим все пути, которые ведут в Л, не проходя через Е:

Пути через Ж: 2 пути.

Пути через К: 3 пути.

Итого: 2 + 3 = 5 путей.

Ответ: 5