На рисунке - схема дорог, связывающих города А, В, С, D, Е, F, G, Н, К, L, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М?
Начнем считать количество путей с конца маршрута – с города М. NX — количество различных путей из города А в город X, N — общее число путей.
В "М" можно приехать из L, G, H, F или K, поэтому N = NM = NL + NG + N F + NH + NK (1)
Аналогично:
NL = NF + NB;
NG = NF;
NF = NB + NC + NA + ND + NE;
NH = NF;
NK = NF.
Добавим еще вершины:
NB = NA + NC = 1 + 1 = 2;
NC = NA = 1;
ND = NA = 1;
NE = ND + NA = 1 + 1 = 2.
Преобразуем вершины:
NL = NF + NB = 7 + 2 = 9;
NG = NF = 7;
NF = NB + NC + NA + ND + NE = 2 + 1 + 1 + 1 + 2 = 7;
NH = NF = 7;
NK = NF = 7.
Тогда NM = NL + NG + N F + NH + NK = 9 + 7 + 7 + 7 + 7 = 37.