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

Исключим все пути, проходящие через Г, и подсчитаем количество путей до следующих вершин.

1. До Б и Д существует по одному пути: N(Б)=1, N(Д)=1.
2. До В можно прийти непосредственно из А или через Б: N(В)=1+1=2.
3. До Е ведут пути из А, Б и В: N(Е)=1+1+2=4.
4. До Ж ведут пути из В и Е: N(Ж)=2+4=6.
5. До З ведут пути из Б, В, Д и Ж: N(З)=1+2+1+6=10.
6. До И ведут пути из Е, Ж и З: N(И)=4+6+10=20.

Из И в М можно пройти тремя способами: через К непосредственно, через Л непосредственно или через К и затем Л. Поэтому число путей из И в М равно 3.

20·3=60.

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