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

В "М" можно при­е­хать из K, H или L, по­это­му N = N_M = N_K + N_H + N _L (1)

Ана­ло­гич­но:

N_K = N_H + N_P;

N_H = N_F + N_C + N_A + N_D + N_G;

N_L = N_H.

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

N_Р = N_H;

N_F = N_B + N_C;

N_C = N_A = 1;

N_D = N_A = 1;

N_G = N_D + N_E.

N_B = N_A + N_C = 1 + 1 = 2;

N_E = N_D + N_A = 1 + 1 = 2;

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

N_Р = N_H;

N_F = N_B + N_C = 2 + 1 = 3;

N_C = N_A = 1;

N_D = N_A = 1;

N_G = N_D + N_E = 1 + 2 = 3.

N_H = N_F + N_C + N_A + N_D + N_G = 3 + 1 + 1 + 1 + 3 = 9;

N_K = 9 + 9;

N_L = 9.

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

N = 36.

При­ве­дем дру­гое ре­ше­ние.

За­ме­тим, что до­брать­ся из го­ро­да А в город М можно толь­ко через город Н. Сле­до­ва­тель­но, ко­ли­че­ство путей из го­ро­да А в город М равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город Н и ко­ли­че­ства путей из го­ро­да Н в город М.

Най­дем ко­ли­че­ство путей из город А в город Н:

А = 1

С = 1

D = 1

B = A + C = 2

E = A + D = 2

F = B + C = 3

G = D + E = 3

H = A + C + D + F + G = 9.

Най­дем ко­ли­че­ство путей из го­ро­да Н в город М (при этом Н - ис­ход­ный пункт):

Н = 1

P = H = 1

K = H + P = 2

L = H = 1

M = H + L + K = 4.

Тогда ко­ли­че­ство путей из го­ро­да А в город М рано 9 · 4 = 36.