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