백과

그래프 G=(V, E)에서, 노드 υ_i와 υ_i+1, (i=1, 2, …, k-1)를 연결하는 가지(υ_i, υ_i+1)의 계열 P=(υ₁, υ₂), (υ₂, υ₃), …, (υ_k–1, υ_k))를 노드 υ₁에서 노드 υ_k로의 길이 (length) k—1의 경로라고 한다. P에 포함되는 가지의 집합을 경로라 부르는 수도 있다.

G가 유향 그래프인 경우는 P를 유향경로(directed path)라 부른다. P는 노드 υ_i와 가지(υ_i, υ_i+1)를 지나며, υ_i와 υ_b를 연결한다고 한다. 동일 노드를 2회 이상 지나지 않는 경로는 단순(simple)하다고 하며, υ₁=υ_k인 경로를 폐경로(cycle, circuit)라 부른다. 폐경로는 υ₁과 υ_k를 제외하고 동일 노드를 2회 이상 지나지 않을 때 단순하다고 한다.

유향 트리 G=(V, T)에서는, 뿌리 υ₀에서 다른 각 노드 υ를 향해서 꼭 하나의 경로가 있다. 이 경로의 길이를 υ의 깊이(depth)라 부르고, υ에서 잎까지의 가장 긴 경로의 길이를 υ의 높이(height)라 부른다. 또, υ₀의 높이를 트리 G의 높이라 부르고, G의 높이에서 υ의 깊이를 뺀 값을 υ의 레벨(level)이라 부른다. 유향 트리 G=(V, T)에서, 다음과 같이 2종류의 경로길이(path length)가 정의된다.

즉, 뿌리에서 모든 잎으로의 경로의 길이의 총합 L_e를 외부경로길이(external path length), 뿌리에서 잎을 제외한 모든 노드로의 경로의 길이의 총합 L_i를 내부경로길이(internal path length)라 한다. 특히, G가 잎 이외의 각 노드에서 꼭 2개의 가지가 나와있는 것과 같은 2분 트리일 때, 외부경로길이 L_e와 내부경로길이 L_i사이에, L_e=L_e+|V|—1의 관계가 성립한다. 경로길이는, 각종 산법의 실행시간의 해석을 할 때 쓰인다. 〈참조어〉 순서 트리, 내부경로길이, 폐경로