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

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

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

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

Определения

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

След, но не path.svg
Пусть 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 , и открыта в противном случае. Бесконечное блуждание - это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, а полубесконечное блуждание (или луч ) имеет первую вершину, но не последнюю вершину.
  • След прогулка , в которой все ребра различны.
  • Путь представляет собой след , в котором все вершины (и , следовательно, все ребра) различны.

Если 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 i , v i + 1 ) для i = 1, 2,…, n - 1 . ( v 1 , v 2 ,…, v n ) - последовательность вершин направленного блуждания. Бесконечное направленное блуждание - это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, а полубесконечное направленное блуждание (или луч ) имеет первую вершину, но не последнюю вершину.
  • Направленный след является направленной прогулкой , в которой все ребра различны.
  • Ориентированный путь представляет собой ориентированный след , в котором все вершины различны.

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

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

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

Примеры

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

Поиск путей

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

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

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

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

  • Бендер, Эдвард А .; Уильямсон, С. Гилл (2010). Списки, решения и графики. С введением в вероятность .
  • Бонди, JA; Мурти, USR (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.