В теории графов путь в графе — это конечная или бесконечная последовательность ребер , соединяющая последовательность вершин , которые, по большинству определений, все различны (а поскольку вершины различны, то и ребра различны) . Направленный путь (иногда называемый дипутью [1] ) в ориентированном графе — это конечная или бесконечная последовательность ребер, которая соединяет последовательность различных вершин, но с дополнительным ограничением, согласно которому все ребра должны быть направлены в одном направлении.
Пути — это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов. См., например, Bondy & Murty (1976), Gibbons (1985) или Diestel (2005). Корте и др. (1990) охватывают более сложные алгоритмические темы, касающиеся путей в графах.
Пусть G = ( V , E , φ ) — граф. Конечный обход — это последовательность ребер ( e 1 , e 2 , …, e n − 1 ) , для которой существует последовательность вершин ( v 1 , v 2 , …, v n ) такая, что φ ( e i ) = { v я , v я + 1 } для я знак равно 1, 2, …, n - 1 . ( v 1 , v 2 , …, v n ) — последовательность вершин обхода. Проход закрыт , если v 1 = v n , и открыт в противном случае. Бесконечный обход — это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, а полубесконечный обход (или луч ) имеет первую вершину, но не имеет последней вершины.
Тропа — это прогулка , в которой все края различимы. [2]
Путь — это путь, в котором все вершины (а, следовательно , и все ребра) различны. [2]
Если w = ( e 1 , e 2 , …, e n − 1 ) является конечным обходом с последовательностью вершин ( v 1 , v 2 , …, v n ) , то w называется прогулкой от v 1 до v n . Аналогично для тропы или пути. Если между двумя различными вершинами существует конечный путь, то между ними также существует конечный след и конечный путь.
Некоторые авторы не требуют, чтобы все вершины пути были различны, и вместо этого используют термин « простой путь» для обозначения такого пути, в котором все вершины различны.
Взвешенный граф связывает значение ( вес ) с каждым ребром графа. Вес прогулки (или следа, или пути) во взвешенном графе представляет собой сумму весов пройденных ребер. Иногда вместо веса используются слова «стоимость» или «длина» .
Направленная прогулка, направленный след и направленный путь
Направленный обход — это конечная или бесконечная последовательность ребер , направленных в одном направлении и соединяющая последовательность вершин . [2]
Пусть G = ( V , E , φ ) — ориентированный граф. Конечный направленный обход — это последовательность ребер ( e 1 , e 2 , …, e n − 1 ) , для которой существует последовательность вершин ( v 1 , v 2 , …, v n ) такая, что φ ( e i ) знак равно ( v я , v я + 1 ) для я знак равно 1, 2, …, n - 1 . ( v 1 , v 2 , …, v n ) — последовательность вершин направленного обхода. Направленный обход замкнут, если v 1 = v n , и открыт в противном случае. Бесконечный направленный обход — это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, а полубесконечный направленный обход (или луч ) имеет первую вершину, но не имеет последней вершины.
Направленный маршрут — это направленный маршрут, в котором все края различны. [2]
Направленный путь — это направленный путь, в котором все вершины различны. [2]
Если w = ( e 1 , e 2 , …, e n − 1 ) — конечный направленный обход с последовательностью вершин ( v 1 , v 2 , …, v n ) , то w называется блужданием от v 1 до v н . Аналогично для направленного следа или пути. Если между двумя различными вершинами существует конечный направленный путь , то существует также конечный направленный след и конечный направленный путь между ними.
«Простой направленный путь» — это путь, все вершины которого различны.
Взвешенный ориентированный граф связывает значение ( вес ) с каждым ребром ориентированного графа. Вес направленного обхода (или следа, или пути) во взвешенном ориентированном графе представляет собой сумму весов пройденных ребер. Иногда вместо веса используются слова «стоимость» или «длина» .
Примеры
Граф связный, если существуют пути, содержащие каждую пару вершин.
Ориентированный граф является сильно связным, если существуют противоположно ориентированные пути, содержащие каждую пару вершин.
Путь, в котором никакие ребра графа не соединяют две непоследовательные вершины пути, называется индуцированным путем .
Путь, включающий каждую вершину графа без повторений, называется гамильтоновым путем .
Два пути являются вершинно-независимыми (альтернативно, внутренне вершинно-непересекающимися ), если они не имеют общих внутренних вершин. Аналогично, два пути не зависят от ребра (или не пересекаются с ребрами ), если у них нет общего внутреннего ребра. Два внутренне непересекающихся по вершинам пути не пересекаются по ребрам, но обратное не обязательно верно.
Расстояние между двумя вершинами графа — это длина кратчайшего пути между ними, если таковой существует, в противном случае расстояние равно бесконечности .
Диаметр связного графа — это наибольшее расстояние (определенное выше) между парами вершин графа.
Поиск путей
Существует несколько алгоритмов для поиска кратчайших и длиннейших путей в графах с тем важным отличием, что первая задача вычислительно намного проще, чем вторая.
Алгоритм Дейкстры создает список кратчайших путей от исходной вершины до любой другой вершины в ориентированных и неориентированных графах с неотрицательными весами ребер (или без весов ребер), тогда как алгоритм Беллмана – Форда можно применять к ориентированным графам с отрицательными весами ребер. . Алгоритм Флойда – Уоршалла можно использовать для поиска кратчайших путей между всеми парами вершин во взвешенных ориентированных графах.
Проблема с разделом пути
Проблема разделения k-путей — это проблема разделения данного графа на наименьший набор непересекающихся по вершинам путей длиной не более k . [3]
Маккуэйг, Уильям (1992). «Межциклические орграфы» . В Робертсоне, Нил; Сеймур, Пол (ред.). Теория структуры графов . Совместная летняя исследовательская конференция AMS – IMS – SIAM по минорам графов, Сиэтл, 22 июня – 5 июля 1991 г. Американское математическое общество. п. 205.
