На рисунке изображена схема дорог, связывающих торговые точки A, B, C, D, E, F, G. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей от точки A до точки G? На схеме стрелки: A→B, A→C, A→D, B→D, B→E, C→F, D→F, D→G, E→G, F→G.
По определению ориентированного графа ребро со стрелкой можно пройти только в указанном направлении. Разобьём пути по первому шагу из A: он ведёт в B, C или D.
Если первый шаг A→B, из B можно идти через E сразу к G или через D. Через D возможны ещё два окончания: D→G и D→F→G. Получаем три пути: A–B–E–G, A–B–D–G, A–B–D–F–G.
Если первый шаг A→C, единственное продолжение — C→F→G. Это один путь: A–C–F–G.
Если первый шаг A→D, можно идти прямо D→G либо D→F→G. Это ещё два пути: A–D–G и A–D–F–G.
Группы не пересекаются, потому что первые стрелки у них различны. Складываем их количества:
