경로(그래프 이론)
Path (graph theory)
그래프 이론에서, 그래프에서 경로는 대부분의 정의에 의해 모두 구별되는 일련의 꼭지점을 연결하는 유한 또는 무한의 모서리 수열이다.방향 그래프에서 방향 경로(dipath라고도[1] 함)는 일련의 개별 정점을 결합하는 유한 또는 무한의 에지 시퀀스입니다. 단, 에지는 모두 같은 방향으로 향해야 한다는 제한이 추가됩니다.
경로는 그래프 이론의 기본 개념으로, 대부분의 그래프 이론 텍스트의 도입 섹션에서 설명합니다.예를 들어,Bondy and Murty(1976), Gibbons(1985), Diestel(2005).Korte 외 연구진(1990)은 그래프의 경로에 관한 보다 고급 알고리즘 주제를 다룬다.
정의들
도보, 산책로 및 경로
- G = (V, E, θ)를 그래프로 한다.유한 보행은 i = 1, 2, …, n - 1에 대한 θ(ei) = {vi, vi + 1}의 정점(v1, v22, …, vn − 1nn)이 있는 가장자리(e1, e2, …, e)의1 순서이다.걷기는 vn = v이면1 닫히고 그렇지 않으면 열립니다.무한보행은 여기서 설명하는 것과 동일한 유형의 가장자리 시퀀스이지만 첫 번째 또는 마지막 정점이 없으며 반무한보행(또는 광선)에는 첫 번째 정점이 있지만 마지막 정점이 없습니다.
w = (e12, e, …, en − 1)가 꼭지점 시퀀스1 (v2, v, …, vn)를 갖는 유한 보행이라면 w는 v에서1 v까지의n 보행이라고 한다. 마찬가지로 트레일이나 경로도 마찬가지이다.만약 두 개의 다른 꼭지점 사이에 유한한 보행이 있다면, 그 사이에 유한한 트레일과 유한한 경로가 있을 것이다.
일부 저자는 경로의 모든 정점이 구별되어야 한다고 요구하지 않고 대신 모든 정점이 구별되는 경로를 나타내기 위해 단순 경로라는 용어를 사용합니다.
가중 그래프는 값(가중치)을 그래프의 모든 모서리에 연결합니다.가중 그래프에서 워크(또는 트레일 또는 경로)의 가중치는 횡단된 모서리의 가중치의 합입니다.때때로 무게 대신 비용 또는 길이라는 단어가 사용됩니다.
유도 보행, 유도 탐방로 및 유도 경로
- G = (V, E, θ)를 지향 그래프로 한다.유한 방향 보행은 i = 1, 2, …, n - 1에 대한 θ(ei) = (vi, vi + 1, …, v)가 방향 보행의 정점 순서인1 정점 순서22(v, vn, …, vn)가1 있는 가장자리(e1, e2, …, en − 1)이다.v = v이면n 방향1 보행이 닫히고 그렇지 않으면 개방됩니다.무한 방향 보행은 여기서 설명하는 것과 동일한 유형의 모서리 시퀀스이지만 첫 번째 또는 마지막 정점이 없으며, 반무한 방향 보행(또는 광선)에는 첫 번째 정점이 있지만 마지막 정점이 없습니다.
w = (e12, e, …, en − 1n)가 정점 시퀀스 (v1, v2, …, v)를 갖는 유한 방향 보행이라면 w는 v에서1 v까지의n 보행이라고 한다. 방향 추적 또는 경로에 대해서도 이와 유사하게.두 개의 서로 다른 꼭지점 사이에 유한한 방향성 보행이 있는 경우, 유한한 방향성 트레일과 그 사이에 유한한 방향성 패스가 있다.
일부 저자는 방향 경로의 모든 정점이 구별되어야 한다고 요구하지 않고, 대신 그러한 방향 경로를 지칭하기 위해 단순 방향 경로라는 용어를 사용합니다.
가중치 유향 그래프는 값(가중치)을 유향 그래프의 모든 에지와 관련짓습니다.가중 유향 그래프에서 유향 보행(또는 트레일 또는 경로)의 무게는 횡단된 모서리의 가중치의 합이다.때때로 무게 대신 비용 또는 길이라는 단어가 사용됩니다.
예
- 각 정점 쌍을 포함하는 경로가 있는 경우 그래프가 연결됩니다.
- 방향 그래프는 각 정점의 쌍을 포함하는 반대 방향 방향 경로가 있는 경우 강하게 연결됩니다.
- 두 개의 비연속 경로 정점을 연결하는 그래프 가장자리가 없는 경로를 유도 경로라고 합니다.
- 반복 없이 그래프의 모든 정점을 포함하는 경로를 해밀턴 경로라고 합니다.
- 두 경로는 공통의 내부 정점이 없는 경우 정점에 의존하지 않습니다(또는 내부적으로 정점 분리).마찬가지로 두 경로가 공통의 내부 에지가 없는 경우 에지 독립(또는 에지 분리)입니다.두 개의 정점-분리 경로가 내부적으로 에지-분리 경로이지만, 그 반대가 반드시 참인 것은 아닙니다.
- 그래프에서 두 꼭지점 사이의 거리는 두 꼭지점 사이의 최단 경로 길이입니다(있는 경우). 그렇지 않은 경우 거리는 무한입니다.
- 연결된 그래프의 직경은 그래프의 꼭지점 쌍 사이의 가장 큰 거리입니다(위에서 정의).
경로 찾기
그래프에서 가장 짧은 경로와 가장 긴 경로를 찾기 위한 여러 알고리즘이 존재하며, 중요한 차이점은 전자의 문제가 후자의 문제보다 계산적으로 훨씬 쉽다는 것입니다.
Dijkstra의 알고리즘은 음의 에지 가중치가 아닌(또는 에지 가중치가 없는) 방향 및 무방향 그래프에서 소스 정점에서 다른 모든 정점으로 가는 최단 경로 목록을 생성하는 반면, Bellman-Ford 알고리즘은 음의 에지 가중치가 있는 방향 그래프에 적용할 수 있다.Floyd-Warshall 알고리즘을 사용하여 가중치 유향 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾을 수 있습니다.
「 」를 참조해 주세요.
레퍼런스
- Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
- Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. p. 12-21. ISBN 0-444-19451-7.
- Diestel, Reinhard (2005). Graph Theory. Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6.
- Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. pp. 5–6. ISBN 0-521-28881-9.
- Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (1990). Paths, Flows, and VLSI-Layout. Springer-Verlag. ISBN 0-387-52685-4.
