Количество путей в графе — это общее число маршрутов, которые приводят из одной вершины графа к другой его вершине.
Введение
Под путём в графе понимают последовательный набор его вершин, в котором все вершины соединяются со следующей за ней вершиной посредством ребра.
Если 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$.
Рисунок 4. Таблица. Автор24 — интернет-биржа студенческих работ
Итоговый результат тринадцать путей.
