Решение: Количество путей в графе
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?
Решение по шагам
5 шаговДо вершин B, F и E из A существует по одному пути: $A \to B$, $A \to F$, $A \to E$.
До E можно попасть из A, а также через B и F. Поэтому количество путей в E равно $1 + 1 + 1 = 3$.
До G можно попасть из F и E. Количество путей в G равно $1 + 3 = 4$.
До H можно попасть только из G, поэтому количество путей в H равно $4$.
В D ведут дороги из B, C, E, G и H. Количество путей в D равно $1 + 1 + 3 + 4 + 4 = 13$.
Где здесь ошибаются
Не учитывать пути, проходящие через промежуточные вершины E, G и H.
Двигаться по рёбрам против направления стрелок.
Считать одинаковыми пути, проходящие через разные вершины.