Путь (теория графов) - Path (graph theory)

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

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

Пути - это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов. См. Например Бонди и Мурти (1976), Гиббонс (1985) или Дистель (2005). Korte et al. (1990) обложка более продвинутая алгоритмический темы о путях в графах.

Определения

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

След, но не path.svg
Позволять г = (V, E, ϕ) быть графом. Конечное блуждание - это последовательность ребер (е1, е2, …, еп − 1) для которого существует последовательность вершин (v1, v2, …, vп) такой, что ϕ(ея) = {vя, vя + 1} для я = 1, 2, …, п − 1. (v1, v2, …, vп) это последовательность вершин прогулки. Эта прогулка закрыто если v1 = vп, и открыто еще. Бесконечное блуждание - это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, и полубесконечное блуждание (или луч ) имеет первую вершину, но не имеет последней.
  • А след это прогулка, в которой все ребра различны.[2]
  • А дорожка это след, в котором все вершины (а значит, и все ребра) различны.[2]

Если ш = (е1, е2, …, еп − 1) конечное блуждание с последовательностью вершин (v1, v2, …, vп) тогда ш считается ходить от v1 к vп. Аналогично для тропы или тропы. Если между двумя отчетливый вершины, то между ними также есть конечный след и конечный путь.

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

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

Направленная прогулка, тропа, тропинка

  • А направленная прогулка является конечным или бесконечным последовательность из края направлен в том же направлении, которое соединяет последовательность вершины.[2]
Позволять г = (V, E, ϕ) ориентированный граф. Конечная направленная прогулка - это последовательность ребер (е1, е2, …, еп − 1) для которого существует последовательность вершин (v1, v2, …, vп) такой, что ϕ(ея) = (vя, vя + 1) для я = 1, 2, …, п − 1. (v1, v2, …, vп) это последовательность вершин направленной прогулки. Бесконечное направленное блуждание - это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, и полубесконечное направленное блуждание (или луч ) имеет первую вершину, но не имеет последней.
  • А направленный след направленное блуждание, в котором все ребра различны.[2]
  • А направленный путь направленный след, в котором все вершины различны.[2]

Если ш = (е1, е2, …, еп − 1) конечное ориентированное блуждание с последовательностью вершин (v1, v2, …, vп) тогда ш считается ходить от v1 к vп. Аналогично для направленной тропы или тропы. Если существует конечный направленный переход между двумя отчетливый вершины, то существует также конечный направленный след и конечный направленный путь между ними.

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

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

Примеры

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

Поиск путей

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

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

Смотрите также

использованная литература

  1. ^ Теория графической структуры: Материалы совместной летней исследовательской конференции AMS-IMS-SIAM по второстепенным графам, проходившей с 22 июня по 5 июля 1991 г., стр.205
  2. ^ а б c d е ж Бендер и Уильямсон 2010, п. 162.
  • Бендер, Эдвард А .; Уильямсон, С. Гилл (2010). Списки, решения и графики. Знакомство с вероятностью.
  • Bondy, J. A .; Мурти, США (1976). Теория графов с приложениями. Северная Голландия. п.12-21. ISBN  0-444-19451-7.
  • Дистель, Рейнхард (2005). Теория графов. Springer-Verlag. п. 6-9. ISBN  3-540-26182-6.
  • Гиббонс, А. (1985). Алгоритмическая теория графов. Издательство Кембриджского университета. п. 5-6. ISBN  0-521-28881-9.
  • Корте, Бернхард; Ловас, Ласло; Prömel, Hans Jürgen; Шрайвер, Александр (1990). Пути, потоки и макет СБИС. Springer-Verlag. ISBN  0-387-52685-4.