Начнем считать количество путей с конца маршрута – с города М. N_X — количество различных путей из города А в город X, N — общее число путей.

В "М" можно приехать из Д, Е, К или Л, поэтому N = N_М = N_Д + N_Е + N _К + N _Л (1)

Аналогично:

N_Д = N_Г;

N_Е = N_Г + N_Ж + N_К;

N_К = N_И,

N_Л = N_К.

Добавим еще вершины:

N_Г = N_В + N_Ж;

N_Ж = N_В + N_И;

N_И = N_А = 1;

N_В = N_Б + N_А = 2;

N_Б = N_А = 1.

Преобразуем вершины:

N_Г = N_В + N_Ж = 2 + 3 = 5;

N_Ж = N_В + N_И = 2 + 1 = 3;

N_И = N_А = 1;

N_В = N_Б = 1;

N_Б = N_А = 1.

N_Д = N_Г = 5;

N_Е = N_Г + N_Ж + N_К = 5 + 3 + 1 = 9;

N_К = N_И = 1,

N_Л = N_К = 1.

Подставим в формулу (1):

N = N_М = 5 + 9 + 1 + 1 = 16.