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

1. Прочитаем направления дорог.
Нужно посчитать все пути из А в Л. Двигаться можно только по стрелкам. Пересечение линий без обозначенного города не создаёт развилку. Запишем все исходящие дороги с рисунка; каждая стрелка в списке обозначает одну дорогу:
А → Б, В, Г, Д.
Б → В, Е.
В → Г, Е, З.
Г → З.
Д → Г, Ж.
Е → З, И.
Ж → З, К, Л.
З → Л.
И → Л.
К → Л.
Из Л дорог дальше нет.

2. Обоснуем правило подсчёта.
Обозначим N(X) количество путей из А в город X. Для начального города полагаем N(А) = 1: это один способ начать маршрут, ещё не проходя дорог. В любой другой город можно попасть только по одной из входящих в него дорог. Разделим все пути по последней дороге. Эти группы не пересекаются, поэтому N(X) равно сумме N(Y) по всем городам Y с дорогой Y → X. На этой схеме нет направленных циклов. Считаем города в порядке, при котором все предшественники уже обработаны: А, Б, Д, В, Ж, Г, Е, К, З, И, Л.

3. Последовательно найдём число путей.
N(А) = 1.
N(Б) = N(А) = 1 = 1.
N(Д) = N(А) = 1 = 1.
N(В) = N(А) + N(Б) = 1 + 1 = 2.
N(Ж) = N(Д) = 1 = 1.
N(Г) = N(А) + N(В) + N(Д) = 1 + 2 + 1 = 4.
N(Е) = N(Б) + N(В) = 1 + 2 = 3.
N(К) = N(Ж) = 1 = 1.
N(З) = N(В) + N(Г) + N(Е) + N(Ж) = 2 + 4 + 3 + 1 = 10.
N(И) = N(Е) = 3 = 3.
N(Л) = N(Ж) + N(З) + N(И) + N(К) = 1 + 10 + 3 + 1 = 15.
В последней сумме учитываются все входы в конечный город, поэтому получено полное количество маршрутов: 15.

4. Проверка обратным подсчётом.
Теперь обозначим M(X) количество способов дойти из X до Л. В конечном городе M(Л) = 1. Для остальных городов складываем значения M у концов всех исходящих дорог, то есть разделяем пути по первой дороге. Обрабатываем города в обратном порядке:
M(Л) = 1.
M(И) = M(Л) = 1 = 1.
M(З) = M(Л) = 1 = 1.
M(К) = M(Л) = 1 = 1.
M(Е) = M(З) + M(И) = 1 + 1 = 2.
M(Г) = M(З) = 1 = 1.
M(Ж) = M(З) + M(К) + M(Л) = 1 + 1 + 1 = 3.
M(В) = M(Г) + M(Е) + M(З) = 1 + 2 + 1 = 4.
M(Д) = M(Г) + M(Ж) = 1 + 3 = 4.
M(Б) = M(В) + M(Е) = 4 + 2 = 6.
M(А) = M(Б) + M(В) + M(Г) + M(Д) = 6 + 4 + 1 + 4 = 15.
Получили M(А) = N(Л) = 15. Подсчёты от начала и от конца совпали. Каждый маршрут учитывается ровно один раз в соответствующей группе; количество дорог вместо количества путей не подставляем.

Ответ: 15.