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

Обозначим через N(X) количество путей из А в город X. Для каждой вершины складываем количества путей, ведущих в неё.

В города Б и Г можно попасть только из А: N(Б) = 1, N(Г) = 1.

В город В ведут дороги из А, Б и Г, поэтому N(В) = 1 + 1 + 1 = 3.

В город Д ведут дороги из Б и В: N(Д) = 1 + 3 = 4. В город Е ведёт дорога из Г, поэтому N(Е) = 1.

В город Ж ведут дороги из В и Е: N(Ж) = 3 + 1 = 4. В город И ведёт дорога из Д: N(И) = 4.

В город К можно попасть из Д, Е, Ж и И. Следовательно, N(К) = 4 + 1 + 4 + 4 = 13.

Ответ: 13 путей.