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

YanMarkov

11.03.2016

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

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


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

N(ж) = 2 + 1 + 1 = 4

Ответ: 4