경로 (그래프 이론)

그래프 이론에서 경로(經路, )는 같은 꼭짓점을 거듭 거치지 않는 변들의 열이다.

유향 그래프에서 유향 경로 또는 방향 경로, 디패스(dipath, 다이패스)는 간선이 모두 같은 방향을 향하는 제약이 있는, 일련의 꼭짓점을 연결하는 일련의 간선들이다.

단순 경로는 경로 내 중복된 정점이 없는 경로를 말한다.

정의 
그래프 의, 길이 의 유한 경로는 다음 성질을 만족시키는  속의 점렬 이다.
 모든 에 대하여, 라면 이다.
 모든 에 대하여, 이다.
그래프 의 무한 경로는 다음 성질을 만족시키는  속의 무한 점렬 이다.
 모든 에 대하여, 라면 이다.
 모든 에 대하여, 이다.
경로는 유한 경로 또는 무한 경로이다.

정의에 따라, 경로는 같은 꼭짓점을 중복해서 거칠 수 없다. 한붓그리기와 같이 꼭짓점을 중복하지만 변이 중복되지 않는 경우를 트레일()이라고 하고, 변 또한 중복될 수 있는 경우 보행(步行, )이라고 한다.

예 
다음과 같은 그래프를 살펴보자.

여기서 HAB와 HDG는 경로이다. BDEFDC는 꼭짓점 D가 반복되므로 경로가 아니지만 트레일이다. BDEFDB는 변 BD가 반복되므로 트레일이 아니지만 보행이다.

알고리즘 

두 꼭짓점 사이의 최장·최단 경로를 찾는 문제를 생각해 볼 수 있다. P≠NP를 가정하면, 최단 경로를 찾는 것은 최장 경로를 찾는 것보다 더 쉬우며, 데이크스트라 알고리즘을 사용할 수 있다.

같이 보기 
 경로 그래프
 순환 (그래프 이론)
 경로 (위상수학)

각주

외부 링크 
 
 
 

그래프 이론