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

Задача №15. Графы. Поиск количества путей.

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

Рассмотрим простой и эффективный способ решения.

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

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

Пример:

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.

Индекс вершины Ж и будет ответом задачи.

Ответ: 11

Благодарим за то, что пользуйтесь нашими статьями. Информация на странице «Задача №15. Графы. Поиск количества путей.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам. Чтобы успешно сдать необходимые и поступить в ВУЗ или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из разделов нашего сайта.

Задача о числе путей в ациклическом графе

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

Функция [math]\mathrm[/math] принимает граф [math]g[/math] в виде списка смежности, начальную вершину [math]s[/math] и конечную вершину [math]t[/math] .

Время работы данного алгоритма в худшем случае [math]O(Ans)[/math] , где [math]Ans[/math] — число путей в графе из [math]s[/math] в [math]t[/math] . Например, на следующем графе данный алгоритм будет иметь время работы [math]O(2^)[/math] . Если же использовать метод динамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до [math]O(n)[/math] .

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

Пусть [math]P(v)[/math] — число путей от вершины [math] s [/math] до вершины [math] v [/math] . Тогда [math]P(v)[/math] зависит только от вершин, ребра из которых входят в [math]v[/math] . Тогда [math]P(v) = \sum\limits_P(c)[/math] таких [math]c[/math] , что есть ребро из [math]c[/math] в [math]v[/math] . Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что [math]P(s) = 1[/math] . Это позволяет решить задачу методом динамического программирования.

Псевдокод

Пусть [math]s[/math] — стартовая вершина, а [math]t[/math] — конечная, для нее и посчитаем ответ. Будем поддерживать массив [math]d[/math] , где [math]d[v][/math] — число путей из вершины [math] s [/math] до вершины [math]v[/math] и массив [math]w[/math] , где [math]w[v] = true[/math] , если ответ для вершины [math]v[/math] уже посчитан, и [math]w[v] = false[/math] в противном случае. Изначально [math]w[i] = false[/math] для всех вершин [math]i[/math] , кроме [math]s[/math] , а [math]d[s] = 1[/math] . Функция [math]\mathrm[/math] будет возвращать ответ для вершины [math]v[/math] . Удобнее всего это реализовать в виде рекурсивной функции с запоминанием. В этом случае значения массива [math]d[/math] будут вычисляться по мере необходимости и не будут считаться лишний раз:

[math] count(v) = \left \< \begin d[v], & w[v]=true \\ \sum\limits_count(c), & w[v]=false \end \right. [/math]

Значение функции [math]\mathrm[/math] считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра [math]\[/math] . Всего таких ребер для всех вершин в графе [math]O(E)[/math] , следовательно, время работы алгоритма в худшем случае оценивается как [math]O(V+E)[/math] , где [math]V[/math] — число вершин графа, [math]E[/math] — число ребер.

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

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

Изначально массивы [math]d[/math] и [math]w[/math] инициализированы следующим образом:

Сначала функция [math]\mathrm[/math] будет вызвана от вершины [math]T[/math] . Ответ для нее еще не посчитан ( [math]w[T] = false[/math] ), следовательно [math]\mathrm[/math] будет вызвана от вершин [math]3[/math] и [math]4[/math] . Для вершины [math]3[/math] ответ также не посчитан ( [math]w[3] = false[/math] ), следовательно [math]\mathrm[/math] будет вызвана уже для вершин [math]2[/math] и [math]S[/math] . А вот для них ответ мы уже можем узнать: для [math]2[/math] он равен [math]d[S][/math] , так как это [math]S[/math] — единственная вершина, ребро из которой входит в нее. Непосредственно для [math]S[/math] ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:

Теперь мы знаем значения для вершин [math]2[/math] и [math]S[/math] , что позволяет вычислить [math]d[3] = d[2] + d[S] = 2[/math] . Также обновим значения в массиве [math]w[/math] : [math]w[3] = true[/math] .

В самом начале для вычисления [math]d[T][/math] нам требовались значения [math]d[3][/math] и [math]d[4][/math] . Теперь нам известно значение [math]d[3][/math] , поэтому проследим за тем, как будет вычисляться [math]d[4][/math] . [math]\mathrm[/math] , но [math]w[3] = true, w[2] = true[/math] , следовательно значения [math]d[3][/math] и [math]d[2][/math] мы уже знаем, и нам необходимо вызвать [math]\mathrm[/math] . Ответ для этой вершины равен [math]d[S][/math] , так как это единственная вершина, ребро из которой входит в [math]1[/math] . Обновим соответствующие значения массивов [math]d[/math] и [math]w[/math] :

Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины [math]4[/math] . [math]d[4] = d[3] + d[2] + d[1] = 2 + 1 + 1 = 4[/math] :

Наконец, вычислим [math]d[T] = d[3] + d[4] = 2 + 4 = 6[/math] и обновим таблицы [math]d[/math] и [math]w[/math] :

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

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

Количество путей в графе — это общее число маршрутов, которые приводят из одной вершины графа к другой его вершине.

Введение

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

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

Рисунок 1. Путевые маршруты. Автор24 — интернет-биржа студенческих работ

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

$N_X = N_Y + … + N_Z$.

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

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

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

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

Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ

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

Рисунок 3. Таблица. Автор24 — интернет-биржа студенческих работ

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

B9 (высокий уровень, время – 3 мин)

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение (1 вариант, подстановки):

начнем считать количество путей с конца маршрута – с города К

будем обозначать через N_X количество различных путей из города А в город X

общее число путей обозначим через N

по схеме видно, что N_Б = N_Г = 1

очевидно, что если в город X можно приехать только из Y, Z, то N_X = N_Y + N­_Z, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X

поскольку в K можно приехать из Е, Д, Ж или И, поэтому

в город И можно приехать только из Д, поэтому N_И = N_Д

в город Ж можно приехать только из Е и В, поэтому

подставляем результаты пп. 6 и 7 в формулу п. 5:

в город Д можно приехать только из Б и В, поэтому

в город Е можно приехать только из Г, поэтому N­_Е = N_Г так что

по схеме видно, что N_Б = N_Г = 1, кроме того, N_В = 1 + N­_Б + N_Г = 3

окончательно N = 2N_Б + 3N_В + 2N_Г = 2·1 + 3·3 + 2·1 = 13

Решение (2 вариант, удобная форма записи):

Начнем считать количество путей с конца маршрута – с города к

з аписываем для каждой вершины, из каких вершин можно в нее попасть

теперь для удобства «обратного хода» вершины можно отсортировать так 1 , чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А:

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

далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е:

на следующем шаге добавляем вершину И

и, наконец, конечную. вершину

именно в таком порядке мы и будем вычислять количество путей для каждой вершины

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

N = N_К = 4 + 4 + 4 + 1 = 13

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

Возможные ловушки и проблемы:

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

построение полного дерева маршрутов – занятие трудоемкое и достаточно бесперспективное, даже грамотные учителя информатики здесь в большинстве случаев что-то забывают и ошибаются

Р ешение (3 вариант, перебор вершин по алфавиту):

Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть