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

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

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

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

• 1 Определения
  • 1.1 Прогулка, тропа, путь
  • 1.2 Направленная прогулка, след, путь
• 2 Примеры
• 3 Поиск путей
• 4 См. Также
• 5 Ссылки

Прогулка, след, путь

• A прогулка - это конечная или бесконечная последовательность из ребер, которая объединяет последовательность из вершины.

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

• A тропа - это обход, в котором все ребра различны.
• A Путь - это тропа, в которой все вершины (и, следовательно, также все ребра) различны.

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

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

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

Направленный обход, след, путь

• A направленный обход - это конечная или бесконечная последовательность ребер, направленных в одном направлении, которая соединяет последовательность вершины.

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

• A направленная тропа - это направленная прогулка, в которой все ребра различны.
• A направленная тропа - это направленная тропа, в которой все вершины различны.

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

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

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

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

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

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

• Глоссарий теории графов
• Граф путей
• Многоугольная цепочка
• Задача кратчайшего пути
• Задача самого длинного пути
• алгоритм Дейкстры
• алгоритм Беллмана – Форда
• Алгоритм Флойда – Уоршалла
• Самопроизвольный обход
• Граф кратчайшего пути

• Бендер, Эдвард А.; Уильямсон, С. Гилл (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.