경로 (그래프 이론)

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

 정의 
(유향) 그래프 의, 길이 의 (유향) 유한 경로는 다음 성질을 만족시키는  속의 점렬 이다.
 모든 에 대하여, 라면 이다.
 모든 에 대하여, 이다. (유향 그래프의 경우, )
그래프 의 (유향) 무한 경로는 다음 성질을 만족시키는  속의 무한 점렬 이다.
 모든 에 대하여, 라면 이다.
 모든 에 대하여, 이다. (유향 그래프의 경우, )
(유향) 경로는 (유향) 유한 경로 또는 (유향) 무한 경로이다. 경로는 일반적으로 꼭짓점만 나열하여  또는  처럼 나타낸다.

두 꼭짓점 와 를 연결하는 (유향) 경로는 , 인 (유향) 유한 경로 를 뜻한다.

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

 예 
다음과 같은 A~H의 꼭짓점을 가지는 그래프를 살펴보자.
200px
여기서 HAB와 HDG는 경로이다. BDEFDC는 꼭짓점 D가 반복되므로 경로가 아니지만 트레일이다. BDEFDB는 변 BD가 반복되므로 트레일이 아니지만 보행이다.

 관련 개념 
 그래프의 두 꼭짓점 간의 거리는 두 점을 잇는 최단 경로의 길이이다. 두 점을 연결하는 경로가 없는 경우 거리를 무한대로 정의한다.
 임의의 두 꼭짓점을 연결하는 경로가 항상 존재하는 그래프를 연결 그래프라 한다.
 연결 그래프의 지름()은 그래프의 서로 다른 두 꼭짓점 간의 거리가 최대인 값이다.
 유향 그래프에서 임의의 두 꼭짓점 사이에 양쪽 방향으로의 경로가 항상 존재하는 그래프를 강한 연결 그래프라 한다.
 주어진 그래프의 유도 부분 그래프인 경로를 유도 경로라 한다.
 그래프의 모든 꼭짓점을 거치는 경로를 해밀턴 경로라 한다.

 최단 경로 문제 

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

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

 각주 

 외부 링크 




분류:그래프 이론