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

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

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

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

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

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

Ориентированный ациклический граф (направленный ациклический граф, DAG от англ. directed acyclic graph) — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса).

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

На рисунке справа схема дорог Н-ского района изображена в виде графа

Необходимо определить количество путей на маршруте из пункта А в пункт Ж.

Ответ: 11.

• Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом — никуда не двигаясь).
• Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один — вершина A).
• У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.
• Очевидно, можно посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, нельзя посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, рассчитаем индексы всех вершин.
• Индекс вершины Ж равен 11 (см. рис.), и это число будет ответом задачи.