경로

다음 그림에서 경로(path)란 (v₁, v₂), (v₂, v₃), (v₃, v₄)가 집합 E(G)의 원소일 때 v₁에서 v₄까지 정점 순서 v₁->v₂->v₃->v₄를 의미합니다. 이때 경로 길이는 에지 개수입니다. 경로 중에서 단순 경로(simple path)는 어떤 경로에서 처음과 마지막을 제외하고 모든 정점이 다를 때를 의미합니다. 그래프에서 경로라고 하면 일반적으로 단순 경로를 의미합니다. 사이클(cycle)이란 단순 경로에서 처음과 마지막 정점이 같은 것입니다. 그림 6- 6에서는 v₂->v₃->v₄->v₂가 사이클이지요.

▲ 그림 6-6 경로