Задача 7469 На рисунке — схема дорог, связывающих...

YanMarkov

06.03.2016

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

Начнем считать с конца пути.
Пусть N(х) - число путей от а до х, тогда:
N(ж) = N(д) + N(в) + N(е)
N(д) = N(б)
N(е) = N(г)
N(в) = N(б) + N(а) + N(г)
N(б) = N(а)
N(г) = N(а)

N(а) = 1
N(б) = 1
N(г) = 1
N(в) = 1 + 1 + 1 = 3
N(д) = 1
N(е) = 1

N(ж) = 1 + 3 + 1 = 5

Ответ: 5