Сколько путей? Сколько существует путей из вершины A в вершину F?

Ответ: 3 пути.

Это маршруты:

1. \(A \to B \to F\)
2. \(A \to B \to D \to H \to F\)
3. \(A \to B \to D \to E \to C \to F\)

Как рассуждать. Из вершины \(A\) есть только один выход — в \(B\). Дальше:

• из \(B\) можно сразу прийти в \(F\) — это первый путь;
• или пойти \(B \to D\). Из \(D\) есть два варианта:
  • \(D \to H \to F\);
  • \(D \to E \to C \to F\).

Получаем \(1+2=3\) пути.

Почему не больше. В графе есть циклы, например \(B-D-H-F-B\), но путь не должен повторять вершины, а после прихода в \(F\) мы заканчиваем маршрут. Поэтому «кружение» по циклу новых путей не добавляет.

Проверка: все три маршрута проходят только по рёбрам, которые есть на рисунке, и других развилок по дороге нет.