Введение

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

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

Ходьба, тропа и дорожка

Ходьба — это конечная или бесконечная последовательность рёбер, соединяющих последовательность вершин. Пусть G = (V, E, ϕ) — граф. Конечная ходьба — это последовательность рёбер (e1, e2, ..., en-1), для которой существует последовательность вершин (v1, v2, ..., vn) такая, что ϕ(ei) = {vi, vi+1} для i = 1, 2, ..., n-1. (v1, v2, ..., vn) — последовательность вершин ходьбы. Ходьба называется замкнутой, если v1 = vn, и разомкнутой в противном случае. Бесконечная ходьба — это последовательность рёбер того же типа, что и описанная здесь, но без первой или последней вершины, а полубесконечная ходьба (или луч) имеет первую вершину, но не имеет последней вершины. Тропа — это ходьба, в которой все рёбра различны. Путь — это тропа, в которой все вершины (и, следовательно, все рёбра) различны. Если w = (e1, e2, ..., en-1) — конечная ходьба с последовательностью вершин (v1, v2, ..., vn), то w называется ходьбой из v1 в vn. Аналогично для тропы или пути. Если между двумя различными вершинами существует конечная ходьба, то между ними существует также конечная тропа и конечный путь. Некоторые авторы не требуют, чтобы все вершины пути были различными, и вместо этого используют термин простой путь для обозначения пути, в котором все вершины различны. Взвешенный граф связывает значение (вес) с каждым ребром в графе. Вес ходьбы (или тропы, или пути) во взвешенном графе — это сумма весов пройденных рёбер. Иногда вместо веса используются слова «стоимость» или «длина».

Направленная ходьба, направленная тропа и направленная дорожка

Направленная ходьба — это конечная или бесконечная последовательность рёбер, направленных в одном направлении, соединяющих последовательность вершин. Пусть G = (V, E, φ) — направленный граф. Конечная направленная ходьба — это последовательность рёбер (e1, e2, ..., en-1), для которой существует последовательность вершин (v1, v2, ..., vn) такая, что φ(ei) = (vi, vi+1) для i = 1, 2, ..., n-1. (v1, v2, ..., vn) — последовательность вершин направленной ходьбы. Направленная ходьба называется замкнутой, если v1 = vn, и разомкнутой в противном случае. Бесконечная направленная ходьба — это последовательность рёбер того же типа, что и описанная здесь, но без первой или последней вершины, а полубесконечная направленная ходьба (или луч) имеет первую вершину, но не имеет последней вершины. Направленная тропа — это направленная ходьба, в которой все рёбра различны. Направленный путь — это направленная тропа, в которой все вершины различны. Если w = (e1, e2, ..., en-1) — конечная направленная ходьба с последовательностью вершин (v1, v2, ..., vn), то w называется ходьбой из v1 в vn. Аналогично для направленной тропы или пути. Если между двумя различными вершинами существует конечная направленная ходьба, то между ними также существует конечная направленная тропа и конечный направленный путь. "Простой направленный путь" — это путь, в котором все вершины различны. Взвешенный направленный граф связывает значение (вес) с каждым ребром в направленном графе. Вес направленной ходьбы (или тропы, или пути) во взвешенном направленном графе — это сумма весов пройденных рёбер. Иногда вместо веса используются слова "стоимость" или "длина".

Примеры

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

Поиск путей

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

Проблема разделения пути

Проблема разбиения на k-пути — это задача разбиения заданного графа на минимальное количество непересекающихся путей длиной не более k.