경로 (그래프 이론)

그래프 이론에서, 경로(經路, 영어: path 패스^[*])는 같은 꼭짓점을 거듭 거치지 않는, 그래프의 변들의 열이다. 유향 경로(有向經路, 영어: directed path 디렉티드 패스^[*], dipath 디패스^[*])는 같은 꼭짓점을 거듭 거치지 않는, 유향 그래프의 변들의 열이다.

정의

그래프 $G$의, 길이 $n\in \mathbb {N}$의 유한 경로는 다음 성질을 만족시키는 $V(G)$ 속의 점렬 $v_{0},v_{1},\dots ,v_{n}$이다.

• 모든 $i,j=0,\dots ,n$에 대하여, $v_{i}=v_{j}$라면 $i=j$이다.
• 모든 $i=0,\dots ,n-1$에 대하여, $v_{i}v_{i+1}\in E(G)$이다.

그래프 $G$의 무한 경로는 다음 성질을 만족시키는 $V(G)$ 속의 무한 점렬 $v_{0},v_{1},\dots$이다.

• 모든 $i,j=0,\dots$에 대하여, $v_{i}=v_{j}$라면 $i=j$이다.
• 모든 $i=0,\dots$에 대하여, $v_{i}v_{i+1}\in E(G)$이다.

경로는 유한 경로 또는 무한 경로이다.

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

유향 경로

유향 그래프 $G$의, 길이 $n\in \mathbb {N}$의 유한 유향 경로는 다음 성질을 만족시키는 $V(G)$ 속의 점렬 $v_{0},v_{1},\dots ,v_{n}$이다.

• 모든 $i,j=0,\dots ,n$에 대하여, $v_{i}=v_{j}$라면 $i=j$이다.
• 모든 $i=0,\dots ,n-1$에 대하여, $(v_{i},v_{i+1})\in E(G)$이다.

유향 그래프 $G$의 무한 유향 경로는 다음 성질을 만족시키는 $V(G)$ 속의 무한 점렬 $v_{0},v_{1},\dots$이다.

• 모든 $i,j=0,\dots$에 대하여, $v_{i}=v_{j}$라면 $i=j$이다.
• 모든 $i=0,\dots$에 대하여, $v_{i}v_{i+1}\in E(G)$이다.

유향 경로는 유한 경로 또는 무한 경로이다. (무향) 트레일 및 (무향) 보행과 마찬가지로, 유향 트레일(영어: directed trail)과 유향 보행(영어: directed walk)의 개념을 정의할 수 있다.

예

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

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

알고리즘

 이 부분의 본문은 최단 경로 문제입니다.

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

같이 보기

• 경로 그래프
• 순환 (그래프 이론)
• 경로 (위상수학)

외부 링크

• Weisstein, Eric Wolfgang. “Graph path” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Trail” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Walk” (영어). 《Wolfram MathWorld》. Wolfram Research.