Задачи на количество путей

Задачи на количество путей требуют определить, сколькими способами можно попасть из одной вершины ориентированного графа в другую, двигаясь только по направлению стрелок. Основной приём — разбить задачу на подзадачи и последовательно складывать количества путей.

Основные понятия

Сначала повторите, что такое ориентированный граф: его рёбра имеют направление, например \(A \to B\). По ребру можно двигаться только от \(A\) к \(B\), но не обратно. Путь из вершины \(S\) в вершину \(T\) — последовательность рёбер, по которым можно пройти от \(S\) к \(T\). В школьных задачах обычно считают маршруты в ориентированном графе, заданном рисунком, таблицей или описанием переходов.

Не путайте путь с простым путём. В задачах на подсчёт маршрутов иногда разрешается проходить через одну вершину несколько раз, а иногда явно сказано, что повторения запрещены. Если граф ацикличен, повторений всё равно быть не может, поэтому задача особенно удобно решается динамически.

Здесь \(F(X)\) обозначает число путей из начальной вершины \(S\) в вершину \(X\). Начальное значение: \(F(S)=1\). Это означает, что существует один пустой маршрут, который уже находится в \(S\). Для любой вершины, в которую нет пути из \(S\), значение равно нулю.

Динамическое программирование на графе

Динамическое программирование использует уже найденные ответы для более простых подзадач. В ацикличном графе вершины можно обрабатывать слева направо — от старта к финишу. Если порядок неочевиден, помогает топологическая сортировка: каждая дуга направлена из более ранней вершины в более позднюю.

1. Выберите начальную вершину \(S\) и положите \(F(S)=1\).
2. Для остальных вершин сначала установите \(F(V)=0\).
3. Обрабатывайте вершины в порядке от старта к финишу.
4. Для каждой дуги \(U \to V\) прибавляйте \(F(U)\) к \(F(V)\).
5. В конце ответом будет \(F(T)\) для конечной вершины \(T\).

Эта формула смотрит на входящие рёбра. Можно использовать и обратный вариант: обозначить \(G(V)\) как число путей из \(V\) в конечную вершину \(T\). Тогда \(G(T)=1\), а для остальных вершин значение равно сумме по исходящим рёбрам.

Разобранный пример

Рассмотрим граф с вершинами \(S,A,B,C,D,T\) и дугами \(S\to A\), \(S\to B\), \(A\to C\), \(A\to D\), \(B\to C\), \(C\to D\), \(C\to T\), \(D\to T\). Требуется найти количество путей из \(S\) в \(T\).

Как считать по таблице и графу переходов

В экзаменационных задачах граф часто скрыт в таблице: строка обозначает текущую вершину, столбец — следующую, а единица означает разрешённый переход. Иногда вершины — это состояния, пункты, клетки или наборы параметров. Такой объект удобно рассматривать как граф переходов.

Для каждой строки определите, куда можно перейти. Затем перенесите число способов из текущего состояния во все достижимые состояния. Если один переход можно выполнить несколькими способами, его вклад умножается на число вариантов перехода.

Здесь \(m_{UV}\) — число различных переходов из \(U\) в \(V\). В обычном графе без кратных рёбер \(m_{UV}\) равно либо \(0\), либо \(1\).

Для задач на клетки сетки часто разрешены движения только вправо и вниз. Тогда число маршрутов в клетку \((i,j)\) равно сумме числа маршрутов в клетку сверху и в клетку слева. Такой граф автоматически ацикличен, поэтому клетки можно обрабатывать построчно и слева направо.

Когда появляются циклы

Если в графе есть цикл, число маршрутов может быть бесконечным: можно обойти цикл один, два или любое число раз. Поэтому перед подсчётом проверьте, запрещены ли повторения и содержит ли граф циклы. Если требуется считать только простые пути, задача существенно сложнее обычного динамического программирования.

Алгоритм и проверка результата

Если граф задан списком рёбер, можно применять следующий универсальный алгоритм: построить порядок вершин от старта к финишу, записать единицу в стартовой вершине, затем пройти все рёбра в этом порядке. Время работы пропорционально числу вершин и рёбер, то есть перебор всех маршрутов не требуется.

для всех вершин V: F[V] := 0
F[S] := 1
для вершин U в порядке от S к T:
    для каждого ребра U -> V:
        F[V] := F[V] + F[U]
вывести F[T]

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