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

Подсчитаем число направленных путей из А в Е и из Е в М.

До Е ведут три дороги через В (из А в В, затем в Е), а также два пути через Б: А → Б → Е и А → Б → В → Е. Итого путей из А в Е: 5.

Из Е в З можно попасть двумя способами: непосредственно или через Ж. Из З в М ведут три пути: непосредственно через К, через И и К, либо через Л. Значит, из Е в М существует 2 × 3 = 6 путей.

Каждый путь из А в М через Е составляется выбором пути до Е и пути от Е до М: 5 × 6 = 30.

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