Как найти число путей в графе

Введение

Если G является неориентированным графом, то путём в графе G будет такой конечный или бесконечный набор последовательных рёбер и вершин S = (…, a0, E0, a1, E1, …, En-1, an), для которого пара соседних рёбер Ei и Ei-1 обладают общей вершиной ai. То есть справедливы следующие выражения E0 = (a0, a1), E1 = (a1, a2), …, En = (an, an+1)

Следует заметить, что возможна неоднократная встреча с одним и тем же ребром при прохождении путевого маршрута. В случае, когда нет рёбер, которые предшествуют E0, то a0 считается исходной вершиной S. А когда не существует рёбер, которые идут за E(n-1), то an считается последней вершиной S. Все вершины, которые принадлежат паре соседних рёбер, считаются внутренними.

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

При совпадении начальной и конечной вершин, путь считается циклическим. В случае, когда каждое ребро графа при обходе путевого маршрута, попадается всего один раз (повтор вершин допускается), такой путь считается цепью, а циклический путь считается циклом.

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

Количество путей в графе

В случае, когда в город S возможно доехать лишь из городов X, Y, и Z, то количество разнообразных путевых маршрутов из города А в город S равняется суммарному количеству разных путей движения из А в Х, из А в Y и из А в Z, что можно выразить следующей формулой:

$N_S = N_X + N_Y + N_Z$

Обозначим как NM количество путевых маршрутов из вершины А в некую вершину М. Количество путей будет конечным, если в графе отсутствуют замкнутые пути, то есть циклы. Рассмотрим конкретный пример. Имеется структурная схема дорог, которые соединяют города А, Б, В, Г, Д, Е, Ж, И, К, Л. Передвижение по всем дорогам возможно только в одну сторону, в которую указывает стрелка. Необходимо определить количество возможных путей из города А в город Л.

Обозначим как $N_X$ число разных маршрутов из города А в город Х. Считаем, что город А является исходным пунктом путевого маршрута, и, следовательно, NA = 1. А для произвольно выбранного города Х число путей $N_X$ возможно определить по формуле:

$N_X = N_Y + … + N_Z$.

Здесь суммарный путь принят по всем вершинам, имеющим прямую связь с вершиной Х, то есть, к примеру:

$N_Л = N_Д + N_И + N_Ж + N_К$

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

В пункты Б и В ведут единственные дороги из А. В пункт В можно попасть из пунктов А, Б, и Г, т.е. $N_В = N_А + N_Б + N_Г = 3$.

В пункт Е можно попасть только из Г, количество путей равно количеству путей в пункт Г. В пункт Ж ведут прямые пути из пунктов Е и В, т.е. $N_Ж = N_В + N_Е = 4$. В пункт Д ведут прямые пути из пунктов Б и В, т.е. $N_Д = N_В + N_Б = 4$.

В пункт И можно попасть только из Д, количество путей равно количеству путей в пункт Д = 4. В пункт К ведет путь только из пункта Е, т.е. $N_К = N_Е = 1$. В пункт Л ведут прямые пути из пунктов Д, И, Ж и К, т.е. $N_Л = N_Д + N_И + N_Ж + N_К = 13$.

Итоговый результат тринадцать путей.

Решение задачи

Перебор всех возможных путей

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

Функция принимает граф в виде списка смежности, начальную вершину и конечную вершину .

countPaths(g, v, t)
    if v == t
        return 1
    else
        s = 0
        for to in g[v]
            s += countPaths(g, to, t)
        return s

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

Метод динамического программирования

Пусть — число путей от вершины до вершины .
Тогда зависит только от вершин, ребра из которых входят в . Тогда таких , что есть ребро из в . Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что . Это позволяет решить задачу методом динамического программирования.

Псевдокод

Пусть — стартовая вершина, а — конечная, для нее и посчитаем ответ. Будем поддерживать массив , где — число путей из вершины до вершины и массив , где , если ответ для вершины уже посчитан, и в противном случае. Изначально для всех вершин , кроме , а . Функция будет возвращать ответ для вершины . Удобнее всего это реализовать в виде рекурсивной функции с запоминанием. В этом случае значения массива будут вычисляться по мере необходимости и не будут считаться лишний раз:

count(g, v)
    if w[v]
        return d[v]
    else
        sum = 0
        w[v] = true
        for c in g[v]
            sum += count(g, c)
        d[v] = sum
        return sum

countPaths(g, s, t)
    d[s] = 1
    w[s] = true
    answer = count(t)
    return answer

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

Пример работы

Рассмотрим пример работы алгоритма на следующем графе:

Изначально массивы и инициализированы следующим образом:

Сначала функция будет вызвана от вершины . Ответ для нее еще не посчитан (), следовательно будет вызвана от вершин и . Для вершины ответ также не посчитан (), следовательно будет вызвана уже для вершин и . А вот для них ответ мы уже можем узнать: для он равен , так как это — единственная вершина, ребро из которой входит в нее. Непосредственно для ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:

Теперь мы знаем значения для вершин и , что позволяет вычислить . Также обновим значения в массиве : .

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

Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины . :

Наконец, вычислим и обновим таблицы и :

Этот алгоритм позволяет вычислить количество путей от какой-либо вершины не только до , но и для любой вершины, лежащей на любом из путей от до . Для этого достаточно взять значение в соответствующей ячейке .

См. также

• Динамическое программирование
• Кратчайший путь в ациклическом графе
• Задача о расстановке знаков в выражении
• Задача о порядке перемножения матриц

Источники информации

• Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9..