На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, не проходящих через город Г?
(Текст на фото очень бледный, переписан по смыслу. Дороги со схемы: А→Б, А→В, Б→Г, В→Г, В→Д, Г→Д, Д→Е, Д→Ж, Е→Ж, Ж→З, Ж→И, З→К, И→К.)
Город Г запрещён, поэтому дороги Б→Г, В→Г и Г→Д не используем.
Из Б дорога ведёт только в Г, значит Б — тупик, и путь через Б до К не дойдёт. Из А можно идти только в В.
Обозначим
Пути: А–В–Д–Ж–З–К, А–В–Д–Ж–И–К, А–В–Д–Е–Ж–З–К, А–В–Д–Е–Ж–И–К.
Число путей в вершину равно сумме чисел путей во все вершины, из которых в неё входят дороги. Запрещённую вершину из подсчёта исключают.
