경로 (그래프 이론)

그래프 이론에서 경로(經路, 영어: path 패스[*])는 같은 꼭짓점을 거듭 거치지 않는 변들의 열이다.

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

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

정의

편집

그래프  의, 길이  유한 경로는 다음 성질을 만족시키는   속의 점렬  이다.

  • 모든  에 대하여,  라면  이다.
  • 모든  에 대하여,  이다.

그래프  무한 경로는 다음 성질을 만족시키는   속의 무한 점렬  이다.

  • 모든  에 대하여,  라면  이다.
  • 모든  에 대하여,  이다.

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

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

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

 

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

알고리즘

편집

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

같이 보기

편집

각주

편집
  1. Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991,, p.205

외부 링크

편집