Jump to content

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

Трехмерный граф гиперкуба, показывающий гамильтонов путь красным цветом и самый длинный индуцированный путь жирным черным цветом.

В теории графов путь , которые, по большинству определений в графе — это конечная или бесконечная последовательность ребер , соединяющая последовательность вершин , все различны (а поскольку вершины различны, то и ребра различны). ( Направленный путь иногда называемый dipath [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 . Аналогично для тропы или пути. вершинами существует конечный путь Если между двумя различными , то между ними также существует конечный след и конечный путь.

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

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

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

[ редактировать ]
Пусть 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]

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Маккуэйг 1992 , с. 205.
  2. ^ Jump up to: а б с д и ж Бендер и Уильямсон 2010 , с. 162.
  3. ^ Чен, Юн; Гебель, Рэнди; Линь, Гохуэй; Су, Бинг; Сюй, Яо; Чжан, Ань (01 июля 2019 г.). «Улучшенный алгоритм аппроксимации задачи минимального трехпутевого разбиения» . Журнал комбинаторной оптимизации . 38 (1): 150–164. дои : 10.1007/s10878-018-00372-z . ISSN   1382-6905 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 890273c62b6940e8fdecafccdf6cbdc0__1712922060
URL1:https://arc.ask3.ru/arc/aa/89/c0/890273c62b6940e8fdecafccdf6cbdc0.html
Заголовок, (Title) документа по адресу, URL1:
Path (graph theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)