Задание 9 ОГЭ: количество путей в графе

Количество путей в графе. Тема номера — количество путей в графе. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город K, не проходящих через город C?

Решение

Считаем для каждого города число путей из A: оно равно сумме чисел у городов, из которых в него ведут дороги.

B = A = 1
C: город исключён, 0
D = 0 = 0
E = B = 1
F = D + E = 1
G = E + F = 2
H = E + F + G = 4
K = F + H = 5

Ответ: 5.

Решить такую задачу — новый вариант с проверкой