В теории графов путь в графе — это конечная или бесконечная последовательность ребер , которая соединяет последовательность вершин , которые, согласно большинству определений, все различны (и поскольку вершины различны, то и ребра тоже различны). Направленный путь ( иногда называемый дипутом [1] ) в ориентированном графе — это конечная или бесконечная последовательность ребер, которая соединяет последовательность различных вершин, но с дополнительным ограничением, что все ребра должны быть направлены в одном направлении.
Пути являются фундаментальными концепциями теории графов, описанными во вводных разделах большинства текстов по теории графов. См., например, Bondy & Murty (1976), Gibbons (1985) или Diestel (2005). Korte et al. (1990) рассматривают более сложные алгоритмические темы, касающиеся путей в графах.
Определения
Прогулка, тропа и дорожка
Прогулка — это конечная или бесконечная последовательность ребер , которая соединяет последовательность вершин . [2]
Пусть G = ( V , E , ϕ ) — граф. Конечный маршрут — это последовательность ребер ( e 1 , e 2 , …, e n − 1 ), для которой существует последовательность вершин ( v 1 , v 2 , …, v n ) такая, что ϕ ( e i ) = { v i , v i + 1 } для i = 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 i , v i + 1 ) для i = 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 . Аналогично для направленного пути или пути. Если существует конечный направленный маршрут между двумя различными вершинами, то также существует конечный направленный путь и конечный направленный путь между ними.
«Простой направленный путь» — это путь, в котором все вершины различны.
Взвешенный ориентированный граф связывает значение ( вес ) с каждым ребром в ориентированном графе. Вес направленного обхода (или тропы, или пути) во взвешенном ориентированном графе является суммой весов пройденных ребер. Иногда вместо веса используются слова стоимость или длина .
Примеры
Граф связен , если существуют пути, содержащие каждую пару вершин.
Ориентированный граф является сильно связным , если существуют противоположно ориентированные направленные пути, содержащие каждую пару вершин.
Путь, в котором ни одно ребро графа не соединяет две непоследовательные вершины пути, называется индуцированным путем .
Путь, включающий каждую вершину графа без повторений, называется гамильтоновым путем .
Два пути являются вершинно-независимыми (иначе говоря, внутренне непересекающимися или внутренне вершинно-непересекающимися ), если у них нет общих внутренних вершин или ребер. Аналогично, два пути являются рёберно-независимыми (или рёберно-непересекающимися ), если у них нет общих ребер. Два внутренне непересекающихся пути являются рёберно-непересекающимися, но обратное не обязательно верно.
Расстояние между двумя вершинами в графе — это длина кратчайшего пути между ними, если таковой существует, в противном случае расстояние равно бесконечности .
Диаметр связного графа — это наибольшее расстояние (определенное выше) между парами вершин графа.
Поиск путей
Существует несколько алгоритмов для поиска кратчайших и длинных путей в графах, с важным отличием: первая задача вычислительно намного проще второй.
Алгоритм Дейкстры создает список кратчайших путей от исходной вершины до каждой другой вершины в ориентированных и неориентированных графах с неотрицательными весами ребер (или без весов ребер), в то время как алгоритм Беллмана–Форда может быть применен к ориентированным графам с отрицательными весами ребер. Алгоритм Флойда–Уоршелла может быть использован для поиска кратчайших путей между всеми парами вершин во взвешенных ориентированных графах.
Проблема разделения пути
Задача разбиения k-путей — это задача разбиения заданного графа на наименьший набор вершинно-непересекающихся путей длины не более k . [3]
McCuaig, William (1992). "Intercyclic Digraphs" . В Robertson, Neil; Seymour, Paul (ред.). Graph Structure Theory . AMS–IMS–SIAM Совместная летняя исследовательская конференция по графовым минорам, Сиэтл, 22 июня – 5 июля 1991 г. Американское математическое общество. стр. 205.
