경로 (그래프 이론)

경로 (그래프 이론)는 그래프 이론에서 정점(vertex)과 간선(edge)을 번갈아 가며 나열한 것으로, 한 정점에서 다른 정점으로 이동하는 방법을 나타낸다. 이는 시작 정점(start vertex)과 끝 정점(end vertex)을 가지며, 경로를 구성하는 간선들의 수로 길이를 측정한다.

가장 일반적인 형태의 경로는 워크(walk)라고 불리기도 하며, 정점이나 간선이 반복될 수 있다. 그러나 일반적으로 '경로'라고 할 때는 정점이 반복되지 않는 단순 경로(simple path)를 의미하는 경우가 많다. 단순 경로는 어떤 정점도 두 번 이상 방문하지 않으며, 각 간선도 한 번만 사용된다.

경로의 길이는 경로를 구성하는 간선의 총 개수를 말한다. 가중치 그래프(weighted graph)에서는 각 간선에 할당된 가중치(weight)의 합이 경로의 길이가 될 수 있다.

경로와 유사한 개념으로는 트레일(trail)이 있는데, 트레일은 정점은 반복될 수 있으나 간선은 반복되지 않는 경로이다. 만약 경로의 시작 정점과 끝 정점이 동일하다면 이를 닫힌 경로(closed path) 또는 사이클(cycle)이라고 부른다. 특히, 시작 정점과 끝 정점을 제외한 다른 정점들이 반복되지 않는 사이클을 단순 사이클(simple cycle)이라고 한다. 방향 그래프(directed graph)에서의 경로는 간선의 방향을 따라 이동해야 한다.

그래프 이론에서 경로는 두 정점 간의 연결성(connectivity)을 판단하는 중요한 개념이다. 또한, 최단 경로 문제(shortest path problem)는 경로와 관련된 가장 중요한 문제 중 하나로, 두 정점 사이의 가장 짧은 경로를 찾는 데 사용된다. 이러한 문제 해결을 위해 다익스트라 알고리즘(Dijkstra's algorithm), 벨만-포드 알고리즘(Bellman-Ford algorithm) 등 다양한 알고리즘이 개발되었다.

둘러보기

더 찾아볼 만한 주제