На рисунке -схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, не проходящих через город Г?

Для решения этой задачи нам нужно посчитать количество путей из города А в город К, избегая города Г. Рассмотрим все возможные пути:

1. A -> Б -> Д -> Ж -> К


2. A -> Б -> Е -> Ж -> К


3. A -> В -> Д -> Ж -> К


4. A -> В -> Е -> Ж -> К


5. A -> Д -> Ж -> К (не подходит, т.к. нет прямого пути из А в Д)

С учетом того, что мы не должны проходить через город Г, рассмотрим пути подробнее:

• A -> Б -> Д -> Ж -> К (этот путь возможен)


• A -> Б -> Е -> Ж -> К (этот путь возможен)


• A -> В -> Д -> Ж -> К (Этот путь не подходит, потому что после В можно попасть только в Г)


• A -> В -> Е -> Ж -> К (Этот путь не подходит, потому что после В можно попасть только в Г)

Также стоит рассмотреть вариант прямого пути из А в Д или Е, но как указано выше, из А в Д прямого пути нет.

Однако из А в Е есть прямой путь. Таким образом:

• A -> E -> Ж -> K

Итого получаем три возможных пути:

1. A -> Б -> Д -> Ж -> К


2. A -> Б -> Е -> Ж -> К


3. A -> E -> Ж -> K

Ответ: 3