Задание OGEINF3178BD: Количество путей в графе

1. Прочитаем направления дорог.
Нужно посчитать все пути из A в F. Двигаться можно только по стрелкам. Пересечение линий без обозначенного города не создаёт развилку. Запишем все исходящие дороги с рисунка; каждая стрелка в списке обозначает одну дорогу:
A → B, C, D, E.
B → F.
C → G.
D → E, G.
E → G, H.
Из F дорог дальше нет.
G → F.
H → F, G.

2. Обоснуем правило подсчёта.
Обозначим N(X) количество путей из A в город X. Для начального города полагаем N(A) = 1: это один способ начать маршрут, ещё не проходя дорог. В любой другой город можно попасть только по одной из входящих в него дорог. Разделим все пути по последней дороге. Эти группы не пересекаются, поэтому N(X) равно сумме N(Y) по всем городам Y с дорогой Y → X. На этой схеме нет направленных циклов. Считаем города в порядке, при котором все предшественники уже обработаны: A, B, C, D, E, H, G, F.

3. Последовательно найдём число путей.
N(A) = 1.
N(B) = N(A) = 1 = 1.
N(C) = N(A) = 1 = 1.
N(D) = N(A) = 1 = 1.
N(E) = N(A) + N(D) = 1 + 1 = 2.
N(H) = N(E) = 2 = 2.
N(G) = N(C) + N(D) + N(E) + N(H) = 1 + 1 + 2 + 2 = 6.
N(F) = N(B) + N(G) + N(H) = 1 + 6 + 2 = 9.
В последней сумме учитываются все входы в конечный город, поэтому получено полное количество маршрутов: 9.

4. Проверка обратным подсчётом.
Теперь обозначим M(X) количество способов дойти из X до F. В конечном городе M(F) = 1. Для остальных городов складываем значения M у концов всех исходящих дорог, то есть разделяем пути по первой дороге. Обрабатываем города в обратном порядке:
M(F) = 1.
M(G) = M(F) = 1 = 1.
M(H) = M(F) + M(G) = 1 + 1 = 2.
M(E) = M(G) + M(H) = 1 + 2 = 3.
M(D) = M(E) + M(G) = 3 + 1 = 4.
M(C) = M(G) = 1 = 1.
M(B) = M(F) = 1 = 1.
M(A) = M(B) + M(C) + M(D) + M(E) = 1 + 1 + 4 + 3 = 9.
Получили M(A) = N(F) = 9. Подсчёты от начала и от конца совпали. Каждый маршрут учитывается ровно один раз в соответствующей группе; количество дорог вместо количества путей не подставляем.

Ответ: 9.