Путь (теория графов)

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

Пути — это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов. См., например, Bondy & Murty (1976) , Gibbons (1985) или Diestel (2005) . Корте и др. (1990) охватывают более сложные алгоритмические темы, касающиеся путей в графах.

Определения

Прогулка, тропа и путь

Маршрут — это конечная или бесконечная последовательность ребер , соединяющая последовательность вершин . ^[2]

Пусть G = ( V , E , φ ) — граф. Конечный обход — это последовательность ребер ( e ₁ , e ₂ , …, e _{n − 1} ), для которой существует последовательность вершин ( v ₁ , v ₂ , …, v _n ) такая, что φ ( e _i ) = { v _я , v _{я + 1} } для я знак равно 1, 2, …, n - 1 . ( v ₁ , v ₂ , …, v _n ) — последовательность вершин обхода. Проход закрыт, если v ₁ = v _n , и открыт в противном случае. Бесконечный обход — это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, а полубесконечный обход (или луч ) имеет первую вершину, но не имеет последней вершины.

Тропа — это прогулка , в которой все края различимы. ^[2]
Путь — это путь , в котором все вершины (а, следовательно, и все ребра) различны. ^[2]

Если w = ( e ₁ , e ₂ , …, e _{n − 1} ) является конечным обходом с последовательностью вершин ( v ₁ , v ₂ , …, v _n ), то w называется прогулкой от v ₁ до v _n . Аналогично для тропы или пути. вершинами существует конечный путь Если между двумя различными , то между ними также существует конечный след и конечный путь.

Некоторые авторы не требуют, чтобы все вершины пути были различны, и вместо этого используют термин « простой путь» для обозначения такого пути, в котором все вершины различны.

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

Направленная прогулка, направленный след и направленный путь

Направленный обход — это конечная или бесконечная последовательность ребер , направленных в одном направлении и соединяющая последовательность вершин . ^[2]

Пусть G = ( V , E , φ ) — ориентированный граф. Конечный направленный обход — это последовательность ребер ( e ₁ , e ₂ , …, e _{n − 1} ), для которой существует последовательность вершин ( v ₁ , v ₂ , …, v _n ) такая, что φ ( e _i ) знак равно ( v _я , v _{я + 1} ) для я знак равно 1, 2, …, n - 1 . ( v ₁ , v ₂ , …, v _n ) — последовательность вершин направленного обхода. Направленный обход замкнут , если v ₁ = v _n , и открыт в противном случае. Бесконечный направленный обход — это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, а полубесконечный направленный обход (или луч ) имеет первую вершину, но не имеет последней вершины.

— Направленный маршрут это направленный маршрут, в котором все края различны. ^[2]
Направленный путь — это направленный путь, в котором все вершины различны. ^[2]

Если w = ( e ₁ , e ₂ , …, e _{n − 1} ) — конечный направленный обход с последовательностью вершин ( v ₁ , v ₂ , …, v _n ), то w называется блужданием от v ₁ до v _н . Аналогично для направленного следа или пути. вершинами существует конечный направленный путь Если между двумя различными , то существует также конечный направленный след и конечный направленный путь между ними.

«Простой направленный путь» — это путь, все вершины которого различны.

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

Примеры

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

Поиск путей

Существует несколько алгоритмов для поиска кратчайших и длиннейших путей в графах с тем важным отличием, что первая задача вычислительно намного проще, чем вторая.

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

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

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

См. также

Примечания

^ Маккуэйг 1992 , с. 205.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Бендер и Уильямсон 2010 , с. 162.
^ Чен, Юн; Гебель, Рэнди; Линь, Гохуэй; Су, Бинг; Сюй, Яо; Чжан, Ань (01 июля 2019 г.). «Улучшенный алгоритм аппроксимации задачи минимального трехпутевого разбиения» . Журнал комбинаторной оптимизации . 38 (1): 150–164. дои : 10.1007/s10878-018-00372-z . ISSN 1382-6905 .

Ссылки

Бендер, Эдвард А.; Уильямсон, С. Гилл (2010). Списки, решения и графики. С введением в вероятность .
Бонди, Дж.А.; Мурти, USR (1976). Теория графов с приложениями . Северная Голландия. п. 12-21 . ISBN 0-444-19451-7 .
Дистель, Рейнхард (2005). Теория графов . Издательство Спрингер. стр. 6–9. ISBN 3-540-26182-6 .
Гиббонс, А. (1985). Алгоритмическая теория графов . Издательство Кембриджского университета. стр. 5–6. ISBN 0-521-28881-9 .
Корте, Бернхард ; Ловас, Ласло ; Премель, Ханс Юрген; Шрийвер, Александр (1990). Пути, потоки и макет СБИС . Спрингер Верлаг. ISBN 0-387-52685-4 .
Маккуэйг, Уильям (1992). «Межциклические орграфы» . В Робертсоне, Нил; Сеймур, Пол (ред.). Теория структуры графов . Совместная летняя исследовательская конференция AMS – IMS – SIAM по минорам графов, Сиэтл, 22 июня – 5 июля 1991 г. Американское математическое общество. п. 205.

[FOOTNOTEMcCuaig1992205-1] Маккуэйг 1992 , с. 205.

[FOOTNOTEBenderWilliamson2010162-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж Бендер и Уильямсон 2010 , с. 162.

[3] Чен, Юн; Гебель, Рэнди; Линь, Гохуэй; Су, Бинг; Сюй, Яо; Чжан, Ань (01 июля 2019 г.). «Улучшенный алгоритм аппроксимации задачи минимального трехпутевого разбиения» . Журнал комбинаторной оптимизации . 38 (1): 150–164. дои : 10.1007/s10878-018-00372-z . ISSN 1382-6905 .

[1]

[2]

[3]