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

Решение:

Обозначим количество путей из города X в город Y как K(X, Y). Необходимо найти K(A, П) через В.

Сначала найдем количество путей из А в В:

1. K(A, Б) = 1
2. K(Б, В) = 1
3. K(A, В) = K(A, Б) * K(Б, В) = 1 * 1 = 1

Теперь найдем количество путей из В в П:

1. K(В, Г) = 1
2. K(Г, Д) = 1
3. K(Д, Е) = 1
4. K(Е, П) = 1
5. K(В, П) = K(В, Г) * K(Г, Д) * K(Д, Е) * K(Е, П) = 1 * 1 * 1 * 1 = 1

K(А, П) через B = K(A, В) * K(В, П) = 1 * 1 = 1

Ответ: 1