Путь (теория графов)
В теории графов путь , которые, по большинству определений в графе — это конечная или бесконечная последовательность ребер , соединяющая последовательность вершин , все различны (а поскольку вершины различны, то и ребра различны). ( Направленный путь иногда называемый dipath [1] ) в ориентированном графе — это конечная или бесконечная последовательность ребер, соединяющая последовательность различных вершин, но с дополнительным ограничением, согласно которому все ребра должны быть направлены в одном направлении.
Пути — это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов. См., например, Bondy & Murty (1976) , Gibbons (1985) или Diestel (2005) . Корте и др. (1990) охватывают более сложные алгоритмические темы, касающиеся путей в графах.
Определения
[ редактировать ]Прогулка, тропа и путь
[ редактировать ]- Маршрут — это конечная или бесконечная последовательность ребер , соединяющая последовательность вершин . [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 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 , с. 205.
- ^ Jump up to: а б с д и ж Бендер и Уильямсон 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.