В теории графов , А путь в графе является конечной или бесконечной последовательностью из ребер , которая соединяет последовательность вершин , которые, в большинстве определений, все различны (и так как вершины различны, поэтому являются ребром). Ориентированный путь (иногда называемый dipath [1] ) в ориентированном графе является конечным или бесконечной последовательностью ребер , которая соединяет последовательность различных вершин, но с дополнительным ограничением , что края быть все направлены в том же направлении.
Пути - это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов. См., Например, Бонди и Мурти (1976), Гиббонс (1985) или Дистел (2005). Korte et al. (1990) охватывают более сложные алгоритмические темы, касающиеся путей в графах.
Определения
Прогулка, тропа, тропинка
- Прогулка конечная или бесконечная последовательность из ребер , которая соединяет последовательность вершин . [2]
- Пусть 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 , и открыта в противном случае. Бесконечное блуждание - это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, а полубесконечное блуждание (или луч ) имеет первую вершину, но не последнюю вершину.
- След прогулка , в которой все ребра различны. [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 i , v i + 1 ) для i = 1, 2,…, n - 1 . ( v 1 , v 2 ,…, v n ) - последовательность вершин направленного блуждания. Бесконечное направленное блуждание - это последовательность ребер одного и того же типа, описанного здесь, но без первой или последней вершины, а полубесконечное направленное блуждание (или луч ) имеет первую вершину, но не последнюю вершину.
- Направленный след является направленной прогулкой , в которой все ребра различны. [2]
- Ориентированный путь представляет собой ориентированный след , в котором все вершины различны. [2]
Если 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.